https://algowiki-project.org/w/ru/api.php?action=feedcontributions&user=Lira&feedformat=atomАлговики - Вклад участника [ru]2024-03-29T09:35:25ZВклад участникаMediaWiki 1.34.0https://algowiki-project.org/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Pic_EvenOdd5.png&diff=27337Файл:Pic EvenOdd5.png2019-05-09T20:20:05Z<p>Lira: </p>
<hr />
<div>Сеть четно-нечетной перестановки</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Pic_EvenOdd4.png&diff=27336Файл:Pic EvenOdd4.png2019-05-09T20:19:39Z<p>Lira: </p>
<hr />
<div>Сеть четно-нечетной перестановки</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D1%8C_%D0%BD%D0%B5%D1%87%D0%B5%D1%82%D0%BD%D0%BE-%D1%87%D0%B5%D1%82%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8&diff=27335Сеть нечетно-четной перестановки2019-05-09T20:18:13Z<p>Lira: </p>
<hr />
<div>Сеть нечетно-четной перестановки<br />
<br />
== Описание свойств и структуры алгоритма ==<br />
<br />
=== Словесное описание алгоритма ===<br />
Сеть сортировки размером <math>n</math> задаёт расписание для упорядочивания <math>n</math> элементов массива.<br />
Сеть нечетно-четной перестановки является масштабируемой, поскольку может быть построена для любого числа элементов <math>n \ge 3</math>.<br />
<br />
Сеть состоит из <math>n</math> стадий.<br />
На стадиях с чётными номерами выполняются операции сравнения-перестановки пар элементов с номерами <math> 2*i и 2*i+1 </math>, на стадиях с нечётными номерами <br />
выполняются операции сравнения-перестановки пар элементов с номерами <math> 2*i-1 и 2*i </math>. Пример для <math> n = 4, 5 </math> приведён на рисунках 1 и 2.<br />
<br />
[[Файл:pic_EvenOdd4.png|center|thumb|800px|Рисунок 1. Сеть чётно-нечетной перестановки для 4 элементов]] [[Файл:pic_EvenOdd5.png|center|thumb|800px|Рисунок 2. Сеть чётно-нечетной перестановки для 5 элементов]]<br />
<br />
=== Математическое описание ===<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D1%8C_%D0%BD%D0%B5%D1%87%D0%B5%D1%82%D0%BD%D0%BE-%D1%87%D0%B5%D1%82%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8&diff=27334Сеть нечетно-четной перестановки2019-05-09T20:17:19Z<p>Lira: /* Словесное описание алгоритма */</p>
<hr />
<div>Сеть нечетно-четной перестановки<br />
<br />
== Описание свойств и структуры алгоритма ==<br />
<br />
=== Словесное описание алгоритма ===<br />
Сеть сортировки размером <math>n</math> задаёт расписание для упорядочивания <math>n</math> элементов массива.<br />
Сеть нечетно-четной перестановки является масштабируемой, поскольку может быть построена для любого числа элементов <math>n \ge 3</math>.<br />
<br />
Сеть состоит из <math>n</math> стадий.<br />
На стадиях с чётными номерами выполняются операции сравнения-перестановки пар элементов с номерами <math> 2*i и 2*i+1 </math>, на стадиях с нечётными номерами <br />
выполняются операции сравнения-перестановки пар элементов с номерами <math> 2*i-1 и 2*i </math>. Пример для <math> n = 4, 5 </math> приведён на рисунках 1 и 2.<br />
<br />
[[Файл:pic_EvenOdd4.png|center|thumb|800px|Рисунок 1. Сеть чётно-нечетного слияния для 4 элементов]] [[Файл:pic_EvenOdd5.png|center|thumb|800px|Рисунок 2. Сеть чётно-нечетного слияния для 5 элементов]]<br />
<br />
=== Математическое описание ===<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Pic_EvenOdd5.png&diff=27333Файл:Pic EvenOdd5.png2019-05-09T20:16:37Z<p>Lira: Четно-нечетное слияние</p>
<hr />
<div>Четно-нечетное слияние</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Pic_EvenOdd4.png&diff=27332Файл:Pic EvenOdd4.png2019-05-09T20:14:27Z<p>Lira: Четно-нечетное слияние</p>
<hr />
<div>Четно-нечетное слияние</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D1%8C_%D0%BD%D0%B5%D1%87%D0%B5%D1%82%D0%BD%D0%BE-%D1%87%D0%B5%D1%82%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8&diff=27331Сеть нечетно-четной перестановки2019-05-09T19:24:48Z<p>Lira: </p>
<hr />
<div>Сеть нечетно-четной перестановки<br />
<br />
== Описание свойств и структуры алгоритма ==<br />
<br />
=== Словесное описание алгоритма ===<br />
Сеть сортировки размером <math>n</math> задаёт расписание для упорядочивания <math>n</math> элементов массива.<br />
Сеть нечетно-четной перестановки является масштабируемой, поскольку может быть построена для любого числа элементов <math>n \ge 3</math>.<br />
<br />
Сеть состоит из <math>n</math> стадий.<br />
На стадиях с чётными номерами выполняются операции сравнения-перестановки пар элементов с номерами <math> 2*i и 2*i+1 </math>, на стадиях с нечётными номерами <br />
выполняются операции сравнения-перестановки пар элементов с номерами <math> 2*i-1 и 2*i </math>. Пример для <math> n = 4 </math> приведён на рисунке <br />
<br />
=== Математическое описание ===<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=27328Сети сортировки2019-05-09T18:50:59Z<p>Lira: </p>
<hr />
<div>== Свойства и структура алгоритма ==<br />
=== Общее описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для упорядочивания больших массивов данных с помощью многопроцессорных вычислительных систем. Использование многопроцессорных систем, в ом числе с распределенной оперативной памятью, позволяет достигнуть двух основных целей: 1) снизить время выполнения сортировки; 2) благодаря использованию систем с распределенной оперативной памятью снять ограничение на размер обрабатываемого массива, за счет использования совокупной оперативной памяти всех вычислительных узлов.<br />
Каждая сеть сортировки задаёт расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить масштабируемые сети сортировки, правила создания которых известны для произвольного числа процессоров, и немасштабируемые сети, предназначенные для выполнения только на вычислительных системах некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. Среди немасштабируемых известны [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 10 элементов<ref>Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.</ref>, а так же наилучшие из известных сегодня сетей для 12 и 16 элементов.<br />
<br />
=== Математическое описание алгоритма ===<br />
<br />
Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i \lt j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k \lt j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.<br />
<br />
Пусть число используемых процессоров равно <math>p</math>. Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>0 \le i \le p-1</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|A_j|, |A_i|=|B_i|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
==== Временные материалы (в таком виде их не следует включать) ====<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
<br />
Рассмотрим ряд сетей сортировки в предположении, что на каждой линии сети расположен ровно один элемент массива: <math>n = p</math>:<br />
<br />
[[сеть сортировки простой вставкой]]<br />
<br />
[[сеть нечетно-четной перестановки]]<br />
<br />
[[сеть четно-нечетного слияния Бетчера]]<br />
<br />
[[сеть битонной сортировки]]<br />
<br />
=== Макроструктура алгоритма ===<br />
=== Схема реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Ресурс параллелизма алгоритма ===<br />
=== Входные и выходные данные алгоритма ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация алгоритма ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Локальность данных и вычислений ===<br />
==== Локальность реализации алгоритма ====<br />
===== Структура обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
=== Возможные способы и особенности параллельной реализации алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Масштабируемость алгоритма ====<br />
==== Масштабируемость реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
<br />
== Литература ==<br />
<references /><br />
<br />
<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.<br />
<br />
<br />
[[Категория:Начатые статьи]]<br />
[[Категория:Алгоритмы сортировки]]</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=27327Сети сортировки2019-05-09T18:25:53Z<p>Lira: </p>
<hr />
<div>== Свойства и структура алгоритма ==<br />
=== Общее описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для упорядочивания больших массивов данных с помощью многопроцессорных вычислительных систем. Использование многопроцессорных систем, в ом числе с распределенной оперативной памятью, позволяет достигнуть двух основных целей: 1) снизить время выполнения сортировки; 2) благодаря использованию систем с распределенной оперативной памятью снять ограничение на размер обрабатываемого массива, за счет использования совокупной оперативной памяти всех вычислительных узлов.<br />
Каждая сеть сортировки задаёт расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить масштабируемые сети сортировки, правила создания которых известны для произвольного числа процессоров, и немасштабируемые сети, предназначенные для выполнения только на вычислительных системах некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. Среди немасштабируемых известны [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 10 элементов<ref>Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.</ref>, а так же наилучшие из известных сегодня сетей для 12 и 16 элементов.<br />
<br />
=== Математическое описание алгоритма ===<br />
<br />
Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i \lt j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k \lt j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.<br />
<br />
Пусть число используемых процессоров равно <math>p</math>. Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>0 \le i \le p-1</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|A_j|, |A_i|=|B_i|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
==== Временные материалы (в таком виде их не следует включать) ====<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
<br />
Рассмотрим ряд сетей сортировки в предположении, что на каждой линии сети расположен ровно один элемент массива: <math>n \eq p</math>:<br />
<br />
[[сеть сортировки простой вставкой]]<br />
<br />
[[сеть нечетно-четной перестановки]]<br />
<br />
[[сеть четно-нечетного слияния Бетчера]]<br />
<br />
[[сеть битонной сортировки]]<br />
<br />
=== Макроструктура алгоритма ===<br />
=== Схема реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Ресурс параллелизма алгоритма ===<br />
=== Входные и выходные данные алгоритма ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация алгоритма ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Локальность данных и вычислений ===<br />
==== Локальность реализации алгоритма ====<br />
===== Структура обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
=== Возможные способы и особенности параллельной реализации алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Масштабируемость алгоритма ====<br />
==== Масштабируемость реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
<br />
== Литература ==<br />
<references /><br />
<br />
<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.<br />
<br />
<br />
[[Категория:Начатые статьи]]<br />
[[Категория:Алгоритмы сортировки]]</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=27326Сети сортировки2019-05-09T18:10:23Z<p>Lira: </p>
<hr />
<div>== Свойства и структура алгоритма ==<br />
=== Общее описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для упорядочивания больших массивов данных с помощью многопроцессорных вычислительных систем. Использование многопроцессорных систем, в ом числе с распределенной оперативной памятью, позволяет достигнуть двух основных целей: 1) снизить время выполнения сортировки; 2) благодаря использованию систем с распределенной оперативной памятью снять ограничение на размер обрабатываемого массива, за счет использования совокупной оперативной памяти всех вычислительных узлов.<br />
Каждая сеть сортировки задаёт расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить масштабируемые сети сортировки, правила создания которых известны для произвольного числа процессоров, и немасштабируемые сети, предназначенные для выполнения только на вычислительных системах некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. Среди немасштабируемых известны [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 10 элементов<ref>Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.</ref>, а так же наилучшие из известных сегодня сетей для 12 и 16 элементов.<br />
<br />
=== Математическое описание алгоритма ===<br />
<br />
Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i \lt j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k \lt j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.<br />
<br />
Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|A_j|, |A_i|=|B_i|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
==== Временные материалы (в таком виде их не следует включать) ====<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Макроструктура алгоритма ===<br />
=== Схема реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Ресурс параллелизма алгоритма ===<br />
=== Входные и выходные данные алгоритма ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация алгоритма ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Локальность данных и вычислений ===<br />
==== Локальность реализации алгоритма ====<br />
===== Структура обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
=== Возможные способы и особенности параллельной реализации алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Масштабируемость алгоритма ====<br />
==== Масштабируемость реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
<br />
== Литература ==<br />
<references /><br />
<br />
<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.<br />
<br />
<br />
[[Категория:Начатые статьи]]<br />
[[Категория:Алгоритмы сортировки]]</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=27325Сети сортировки2019-05-09T17:29:52Z<p>Lira: </p>
<hr />
<div>== Свойства и структура алгоритма ==<br />
=== Общее описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для некоторого фиксированного числа элементов.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 элементов<ref>Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.</ref>.<br />
<br />
=== Математическое описание алгоритма ===<br />
<br />
Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i \lt j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k \lt j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.<br />
<br />
==== Временные материалы (в таком виде их не следует включать) ====<br />
<br />
Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|A_j|, |A_i|=|B_i|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Макроструктура алгоритма ===<br />
=== Схема реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Ресурс параллелизма алгоритма ===<br />
=== Входные и выходные данные алгоритма ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация алгоритма ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Локальность данных и вычислений ===<br />
==== Локальность реализации алгоритма ====<br />
===== Структура обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
=== Возможные способы и особенности параллельной реализации алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Масштабируемость алгоритма ====<br />
==== Масштабируемость реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
<br />
== Литература ==<br />
<references /><br />
<br />
<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.<br />
<br />
<br />
[[Категория:Начатые статьи]]<br />
[[Категория:Алгоритмы сортировки]]</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Lira&diff=27324Участник:Lira2019-05-09T17:19:36Z<p>Lira: </p>
<hr />
<div>Якобовский Михаил Владимирович<br />
: член-корреспондент РАН, доктор физико-математических наук, профессор<br />
: заместитель директора по научной работе ИПМ им. М.В. Келдыша РАН<br />
: профессор МФТИ, ФУПМ, кафедра Математического моделирования<br />
: профессор МГУ, ВМиК, кафедры Вычислительных методов, Суперкомпьютеров и квантовой информатики<br />
: mailto:lira@imamod.ru</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:%D0%9C%D0%B0%D0%BA%D1%81%D0%B8%D0%BC&diff=21286Обсуждение участника:Максим2016-12-18T21:17:39Z<p>Lira: /* 1.3 Замечания по содержанию от 2016.12.19 */ новая тема</p>
<hr />
<div>== Статья [[Участник:Максим]] ==<br />
<br />
=== Отсутствующие части ===<br />
* Нет заголовка с названием описываемого алгоритма. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
* В теле статьи не указаны её авторы. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
* Не заполнен раздел 1.10 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
* Отсутствуют заголовки разделов 2.2-2.7 и 3. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
** Замечание не исправлено. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:03, 5 декабря 2016 (MSK)<br />
* Не заполнен раздел 2.7 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
** Замечание не исправлено. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:03, 5 декабря 2016 (MSK)<br />
* Отсутствует список литературы. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
<br />
=== Замечания по тексту ===<br />
* В разделе 1.4 должно быть не перечисление макроопераций, а нужно показать структуру алгоритма на макроуровне. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
* В разделе 1.5 кроме кода нужны также текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
* В разделе 1.6 окончательно не указана последовательная сложность алгоритма. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
* Граф, приведённый в разделе 1.7, не является информационным графом (направленный ациклический граф, вершины - операции, дуги - информационные зависимости). [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:12, 30 ноября 2016 (MSK)<br />
** По графу на рис.1 понять что-либо очень сложно. На рисунки три оси, но вершина расположены в узлах двумерной области. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:03, 5 декабря 2016 (MSK)<br />
* В разделе 1.8 должна быть оценка параллельной сложности алгоритма. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:03, 5 декабря 2016 (MSK)<br />
* В разделе 1.10 должна быть оценка вычислительной мощности алгоритма. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:03, 5 декабря 2016 (MSK)<br />
* В разделе 2.4 не приведены все параметры запуска теста - какой компилятор, с какими опциями использовался, какие версии библиотек, на каких узлах проводился запуск и т.д. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:27, 8 декабря 2016 (MSK) <br />
* В разделе 2.4 не приведена использованная в экспериментах реализация алгоритма. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:27, 8 декабря 2016 (MSK) <br />
** Замечание не исправлено. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 09:52, 13 декабря 2016 (MSK)<br />
* Из графиков в разделе 2.4 следует сделать выводы о масштабируемости реализации. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:27, 8 декабря 2016 (MSK) <br />
* В разделе 2.7 нужно дать ссылки на реализации алгоритма. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 13:27, 8 декабря 2016 (MSK)<br />
* Поскольку не приведена использованная в экспериментах реализация алгоритма, непонятно даже, какие технологии при этом использовались. Опция -fopenmp задаётся для использования OpenMP, а далее написано про использование OpenMPI. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 09:52, 13 декабря 2016 (MSK)<br />
<br />
== 1.3 Замечания по содержанию от 2016.12.19 ==<br />
<br />
Общее замечание<br />
Идея дать функциям разные имена (f,g, ...), а не номера (f1, f2, ...) фактически не позволяет дать описание алгоритма в общем виде.<br />
<br />
Раздел 1.3<br />
Описание вычислительного ядра выглядит непонятно.<br />
<br />
Раздел 1.10<br />
"Параллельная версия алгоритма требует в n раз меньше операций умножения и вычислений значения многомерной функции."<br />
<br />
Это при каком числе процессоров?<br />
<br />
Раздел 2.4<br />
Укажите вид системы уравнений.<br />
<br />
Полагаю, что результаты могут быть существенно улучшены и переведены в ранг содержательных при внесении двух изменений:<br />
<br />
1) Усложнить (с точки зрения времени вычислений) вид правых частей.<br />
<br />
2) Написать и протестировать отдельно программу для общей памяти (оставить только OpenMP).<br />
<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 00:17, 19 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Obirvalger&diff=21241Обсуждение участника:Obirvalger2016-12-18T19:11:37Z<p>Lira: /* Пункт 2.4 */</p>
<hr />
<div>= Пункт 2.4 =<br />
'''принято'''<br />
<br />
== Замечания от 2016_12_11 1 ==<br />
<br />
Раздел 2.3<br />
Совершенно непонятно, как устроена реализация параллельного алгоритма. Имеет ли использованный параллельный алгоритм отношение к <br />
приведенным оценкам вычислительной сложности. <br />
<br />
<br />
Раздел 2.4<br />
Порядок появления в тексте рисунков и их обилие существенно затрудняет анализ результатов, который, кстати не приведён. Выводов нет.<br />
Тем не менее, попробуем.<br />
<br />
Сетка 2000х2000, доменов 10000 <br />
поток 1 2 8<br />
производительность 1.7 2.5 2.5<br />
эффективность 0.17 0.24 0.25<br />
<br />
{| class="wikitable"<br />
|+ Сетка 2000х2000, доменов 10000<br />
|-<br />
! потоков<br />
! 1<br />
! 2<br />
! 8<br />
|-<br />
| производительность<br />
| 1.7<br />
| 2.5<br />
| 2.5<br />
|-<br />
| эффективность<br />
| 0.17<br />
| 0.24<br />
| 0.25<br />
|}<br />
<br />
<br />
Объясните, почему, при одинаковой производительности 2.5 Gflops, <br />
указана одинаковая эффективность 0.25, хотя число потоков отличается в 4 раза?<br />
<br />
Приведите времена работы в секундах.<br />
<br />
Как соотносится таблица с рисунками непонятно. Анализа таблицы тоже нет. Укажите единицы измерения времени (пусть будут секунды). Добавьте номер таблицы.<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 20:51, 11 декабря 2016 (MSK)<br />
<br />
== Замечания от 2016_12_18 1 ==<br />
<br />
Пункт 1.8<br />
Известно [4], что оптимальная параллельная сортировка имеет сложность O(log_2 n)<br />
<br />
Дайте указание на конкретный алгоритм с пояснением, сколько элементов сортируется и сколько процессоров используется. Что известно о соответствующей мультипликативной константе?<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 22:11, 18 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Obirvalger&diff=21240Обсуждение участника:Obirvalger2016-12-18T19:09:18Z<p>Lira: /* Замечания от 2016_12_18 1 */ новая тема</p>
<hr />
<div>= Пункт 2.4 =<br />
'''принято'''<br />
<br />
== Замечания от 2016_12_11 1 ==<br />
<br />
Раздел 2.3<br />
Совершенно непонятно, как устроена реализация параллельного алгоритма. Имеет ли использованный параллельный алгоритм отношение к <br />
приведенным оценкам вычислительной сложности. <br />
<br />
<br />
Раздел 2.4<br />
Порядок появления в тексте рисунков и их обилие существенно затрудняет анализ результатов, который, кстати не приведён. Выводов нет.<br />
Тем не менее, попробуем.<br />
<br />
Сетка 2000х2000, доменов 10000 <br />
поток 1 2 8<br />
производительность 1.7 2.5 2.5<br />
эффективность 0.17 0.24 0.25<br />
<br />
{| class="wikitable"<br />
|+ Сетка 2000х2000, доменов 10000<br />
|-<br />
! потоков<br />
! 1<br />
! 2<br />
! 8<br />
|-<br />
| производительность<br />
| 1.7<br />
| 2.5<br />
| 2.5<br />
|-<br />
| эффективность<br />
| 0.17<br />
| 0.24<br />
| 0.25<br />
|}<br />
<br />
<br />
Объясните, почему, при одинаковой производительности 2.5 Gflops, <br />
указана одинаковая эффективность 0.25, хотя число потоков отличается в 4 раза?<br />
<br />
Приведите времена работы в секундах.<br />
<br />
Как соотносится таблица с рисунками непонятно. Анализа таблицы тоже нет. Укажите единицы измерения времени (пусть будут секунды). Добавьте номер таблицы.<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 20:51, 11 декабря 2016 (MSK)<br />
<br />
== Замечания от 2016_12_18 1 ==<br />
<br />
Пункт 1.8<br />
Известно [4], что оптимальная параллельная сортировка имеет сложность O(log_2 n)<br />
<br />
Дайте указание на конкретный алгоритм с пояснением, сколько элементов сортируется и сколько процессоров используется. Что известно о соответствующей мультипликативной константе?</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Viktorrulev&diff=20664Обсуждение участника:Viktorrulev2016-12-11T20:42:00Z<p>Lira: /* Замечания от 2016_12_11 1 */ новая тема</p>
<hr />
<div>== Статья [[Участник:Viktorrulev/Алгоритм устойчивой кластеризации с иcпользованием связей]] ==<br />
<br />
=== Замечания ===<br />
* Формулы нужно оформить в отдельные блоки для лучшей читаемости [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:13, 23 октября 2016 (MSK)<br />
:: Исправлено (сделать все формулы в одном блоке и выровнять по левой стороне вики не позволяет) [[Участник:Viktorrulev|Viktorrulev]] ([[Обсуждение участника:Viktorrulev|обсуждение]]) 12:18, 26 октября 2016 (MSK)<br />
* В п. 2.7 необходимо указать ссылку на источник [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:13, 23 октября 2016 (MSK)<br />
:: Исправлено [[Участник:Viktorrulev|Viktorrulev]] ([[Обсуждение участника:Viktorrulev|обсуждение]]) 12:18, 26 октября 2016 (MSK)<br />
* В п. 1.5 указать на каком языке представлена реализация [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:13, 23 октября 2016 (MSK)<br />
:: Исправлено [[Участник:Viktorrulev|Viktorrulev]] ([[Обсуждение участника:Viktorrulev|обсуждение]]) 12:18, 26 октября 2016 (MSK)<br />
* В п. в п. 1.7 не указано для каких параметров построен граф. [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:13, 23 октября 2016 (MSK)<br />
:: Исправлено [[Участник:Viktorrulev|Viktorrulev]] ([[Обсуждение участника:Viktorrulev|обсуждение]]) 12:18, 26 октября 2016 (MSK)<br />
* Нужно более полное описание вычислительной мощности алгоритма [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:13, 23 октября 2016 (MSK)<br />
:: Дополнено [[Участник:Viktorrulev|Viktorrulev]] ([[Обсуждение участника:Viktorrulev|обсуждение]]) 12:18, 26 октября 2016 (MSK)<br />
<br />
* Отсутствуют данные по численному эксперименту и масштабируемости. [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 15:01, 22 ноября 2016 (MSK)<br />
<br />
== Замечания от 2016_12_11 1 ==<br />
<br />
<br />
Разделы 1.1, 1.2, 1.3 описывают конкретную область (покупательная корзина и прочее), не имеющую никакого значения с точки зрения математической постановки задачи. Использование термина "транзакция" неоправданно затрудняет восприятие текста. Появляется много терминов, некоторые из к4оторых в контексте суперкомпьютерных технологий имеют совершенно иной, нежели в 'этом тексте смысл. <br />
<br />
Например: <br />
<br />
транзакция - передача блока данных;<br />
<br />
домен - множество вершин расчетной сетки, обрабатываемых одним процессором.<br />
<br />
<br />
Есть граф, вершины, метрика и взвешенные рёбра. Почему нельзя ограничиться этой общепринятой терминологией? <br />
Стоит ли заставлять читателя запоминать термин "домен признака", хотя по существу в статье он не используется?<br />
<br />
<br />
Дополните статью таблицей (хотя бы для двух-трёх размеров графа, например, M=500,1000,1500) с графами: число потоков, время выполнения, ускорение, эффективность.<br />
<br />
Обратите внимание, в тексте нет понятия points, а на графике есть. Используйте одну систему обозначений.<br />
<br />
Раздел 1.6 <br />
Замените текст "имеет такую же вычислительную сложность, как и предыдущий шаг. "<br />
на "имеет сложность O(M). ". Не заставляйте читателя метаться по тексту, ему и так непросто.<br />
<br />
Раздел 1.7 <br />
Оценка сложности перемножения матриц в Вашей статье то <math>O(M^{2.37})</math>, то <math>O(M^2m_{nbr})</math>,<br />
что вполне можно понять, но ссылку на информационный граф перемножения плотных матриц указана на совершенно другой алгоритм, с оценкой <math>O(M^{3})</math>. Определитесь, пожалуйста.<br />
<br />
Если я правильно понял, Вы самостоятельно написали программы. Укажите это явно в разделе 2.4. <br />
<br />
Есть ли соображения, в чём причина отсутствия ускорения на Ломоносове? Какие там времена получились?<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 23:42, 11 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B2_%D0%92._%D0%90.&diff=20652Обсуждение участника:Простов В. А.2016-12-11T20:07:19Z<p>Lira: /* Замечания от 2016_12_11 1 */ новая тема</p>
<hr />
<div>== Статья [[Участник:Tikhomirov.mm/Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK)]] ==<br />
<br />
=== Замечания ===<br />
* Формулы нужно выделить в отдельные блоки для лучшей читаемости [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:00, 23 октября 2016 (MSK)<br />
* Рисунки не подписаны и не пронумерованы [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:00, 23 октября 2016 (MSK)<br />
* Не понятно для каких параметров построен граф [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:00, 23 октября 2016 (MSK)<br />
* нужна более четкая оценка вычислительной мощности алгоритма [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 01:00, 23 октября 2016 (MSK)<br />
* отсутствует краткая сводка свойств алгоритма [[Участник:Teplov|Teplov]] ([[Обсуждение участника:Teplov|обсуждение]]) 02:12, 23 октября 2016 (MSK)<br />
<br />
== Замечания от 2016_12_11 1 ==<br />
<br />
Раздел 1.6<br />
Поясните, пожалуйста, фрагментом псевдокода член <math> n m_m m_a </math> в оценке последовательной сложности.<br />
<br />
Что такое <math>m_i</math> в выражении <math>\min \{ v_m m_i, n \} </math>?<br />
<br />
Предлагаю дополнить статью полным списком обозначений с указанием их смысла.<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 23:07, 11 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Sarseev&diff=20651Обсуждение участника:Sarseev2016-12-11T19:12:19Z<p>Lira: /* Замечания от 2016_12_11 1 */ новая тема</p>
<hr />
<div>п 2.4<br />
<br />
Примечание: задержка с последней правкой вызвана трёхдневным перебоем в работе системы BlueGene, из-за чего было невозможно доделать недостающие графики. --[[Участник:Sarseev|Сергей Арсеев]] ([[Обсуждение участника:Sarseev|обсуждение]]) 22:24, 3 декабря 2016 (MSK)<br />
<br />
* нет пояснений к первым двум графикам - нужно нечто аналогичное пояснению третьего.<br />
<br />
== Замечания от 2016_12_11 1 ==<br />
<br />
Раздел 1.1<br />
"ребром, длина которого ..."<br />
<br />
Лучше не "длина", а "вес".<br />
<br />
Раздел 1.3<br />
<br />
<math>O(|E|*log(|E|)) = O(n^2*log(n^2)) = O(2*n^2*log(n)) = O(n^2*log(n))</math><br />
Так и пишите везде.<br />
<br />
Раздел 1.5<br />
Текст алгоритма не является содержательным.<br />
<br />
Раздел 1.8<br />
<br />
Туманная фраза <br />
"Существуют распределённые алгоритмы построения минимального покрывающего дерева, имеющие асимптотическую сложность <math>O(n*log(n))</math>."<br />
<br />
во-первых, непонятна: что такое <math>n</math>?<br />
<br />
во-вторых, противоречит оценке сложности <math>O(n^2*log(n))</math><br />
<br />
в-третьих, не содержит указания на используемое число процессоров<br />
<br />
в-четвертых, требует указания конкретных ссылок и/или описания соответствующих алгоритмов.<br />
<br />
Раздел 2<br />
<br />
Что и как распараллелено https://github.com/gpiskas/MinSpanTree_Kruskal_MPI_OpenMP?<br />
<br />
Фактически есть три этапа:<br />
<br />
- построение полного графа<br />
<br />
- построение остовного дерева<br />
<br />
- выявление заданного числа рёбер максимальной длинны<br />
<br />
Какова степень параллелизма каждого из этапов?<br />
<br />
Какие параллельные алгоритмы на каждом из этапов использованы и каково ожидаемое ускорение и эффективность на каждом этапе и у всех трёх этапах в совокупности?<br />
<br />
Верно ли, что каждый из этапов имеет оценку вычислительной сложности <math>O(n*log(n))</math>? <br />
<br />
Почему, и при каком числе процессоров?<br />
<br />
<br />
<br />
Пока рисунки "висят в воздухе", вне связи с остальным текстом.<br />
<br />
Сохраняется ли свойство детерминированности алгоритма при параллельной обработке и почему?<br />
<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 22:12, 11 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Obirvalger&diff=20650Обсуждение участника:Obirvalger2016-12-11T17:51:17Z<p>Lira: /* Замечания от 2016_12_11 1 */ новая тема</p>
<hr />
<div>= Пункт 2.4 =<br />
'''принято'''<br />
<br />
== Замечания от 2016_12_11 1 ==<br />
<br />
Раздел 2.3<br />
Совершенно непонятно, как устроена реализация параллельного алгоритма. Имеет ли использованный параллельный алгоритм отношение к <br />
приведенным оценкам вычислительной сложности. <br />
<br />
<br />
Раздел 2.4<br />
Порядок появления в тексте рисунков и их обилие существенно затрудняет анализ результатов, который, кстати не приведён. Выводов нет.<br />
Тем не менее, попробуем.<br />
<br />
Сетка 2000х2000, доменов 10000 <br />
поток 1 2 8<br />
производительность 1.7 2.5 2.5<br />
эффективность 0.17 0.24 0.25<br />
<br />
{| class="wikitable"<br />
|+ Сетка 2000х2000, доменов 10000<br />
|-<br />
! потоков<br />
! 1<br />
! 2<br />
! 8<br />
|-<br />
| производительность<br />
| 1.7<br />
| 2.5<br />
| 2.5<br />
|-<br />
| эффективность<br />
| 0.17<br />
| 0.24<br />
| 0.25<br />
|}<br />
<br />
<br />
Объясните, почему, при одинаковой производительности 2.5 Gflops, <br />
указана одинаковая эффективность 0.25, хотя число потоков отличается в 4 раза?<br />
<br />
Приведите времена работы в секундах.<br />
<br />
Как соотносится таблица с рисунками непонятно. Анализа таблицы тоже нет. Укажите единицы измерения времени (пусть будут секунды). Добавьте номер таблицы.<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 20:51, 11 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Margarita.gabdullina&diff=20624Обсуждение участника:Margarita.gabdullina2016-12-11T14:35:12Z<p>Lira: /* Замечания от 2016_12_11 1 */ новая тема</p>
<hr />
<div>= Вклад = <br />
'''принято''' Необходимо явно указать вклад каждого соавтора.<br />
<br />
= Пункт 1.5 =<br />
'''принято''' Если рисунок не собственный, надо дать ссылку на источник.<br />
<br />
= Пункт 1.7 =<br />
'''принято''' <br />
<br />
+/-Граф следует снабдить пояснением.<br />
+Рисунок следует оформить как рисунок, с номером. Если заимствован, дать ссылку на источник.<br />
<br />
Приведенный рисунок представляет собой некую схему, а требуется привести информационный граф.<br />
<br />
= Пункт 1.10 =<br />
'''принято''' Явно не сказано про мощность алгоритма.<br />
<br />
== Замечания от 2016_12_11 1 ==<br />
<br />
Раздел 1.1<br />
<br />
Заменить "... к более общей задачи - разбиение вершин графа" на " более общей задачЕ - разбиениЮ вершин графа"<br />
<br />
Выбор координаты, вдоль которой вытянута сетка целесообразен только для ограниченного круга сеток, например,<br />
для равномерных сеток с одинаковым шагом по каждой из координат. В общем случае следует сравнивать число разрезанных <br />
рёбер при разрезе по каждой из координат и выбирать наилучший вариант.<br />
<br />
Раздел 1.2<br />
<br />
Требование "Требуется найти такое разбиение множества вершин V на заданное число p связных доменов ..." чрезмерно жесткое.<br />
В общем случает требовать связность доменов не следует, поскольку метод координатной бисекции не содержит действий, направленных на<br />
обеспечение связности. В работе [1] рассматриваются более сложные методы, в том числе, метод инкрементного роста, имеющий в этом отношении более привлекательные характеристики.<br />
<br />
Раздел 1.5<br />
<br />
Описание малых подинтервалов, усложняя алгоритм, по сути добавляет мало. Более того, с точки зрения параллельной обработки не добавляет ничего.<br />
Интересно, почему, у Кнута такой алгоритм не попал в число наиболее привлекательных? Зачем большую часть раздела занимает частный вариант последовательной сортировки?<br />
Откуда вдруг "локальные деревья"? <br />
<br />
"Алгоритм работает только с координатами вершин и не учитывает связи между ними, что делает его экономичным по памяти"<br />
Плохо, как раз следует учитывать связи, иначе, почему число разрезанных рёбер окажется минимизировано.<br />
<br />
Раздел 1.6<br />
<br />
Полезно пояснить, почему верна оценка <math> O(n, p) = n \log_2{n} \log_2{p} </math>.<br />
<math> n \log_2{n} </math> только для первой сортировки, для двух следующих уже <math> (n/2) \log_2{n/2} </math>. <br />
<br />
Раздел 1.7<br />
<br />
Что такое (LS и PS)?<br />
<br />
Раздел 1.8<br />
<br />
"Исходя из того, что метод является геометрическим, алгоритм обладает координатным параллелизмом"<br />
Совсем непонятно! Мы не рассматривали такой параллелизм. Приведите ссылку на источник и прокомментируйте, что это такое.<br />
<br />
"4. Локальная рекурсивная координатная бисекция вершин по доменам"<br />
Не по доменам, а по процессорам.<br />
<br />
Разберитесь, где у Вас процессы, процессоры, домены. Пока каша.<br />
<br />
Введите подраздел с перечислением всех переменных n, p, m, Np. Сложно выискивать их по тексту.<br />
<br />
<br />
Раздел 1.9<br />
<br />
''E'' отсутствует во входных данных.<br />
<br />
Число разрезанных рёбер отсутствует в выходных данных, что не удивительно, поскольку обработка рёбер вообще не предусмотрена и не описана.<br />
<br />
Раздел 1.10<br />
<br />
"Алгоритм устойчив, так как работает с целочисленными данными"<br />
<br />
почему, собственно? Координаты вершин - вешественные числа.<br />
<br />
--[[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 17:35, 11 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Lira&diff=20620Участник:Lira2016-12-11T13:37:33Z<p>Lira: Новая страница: «Якобовский Михаил Владимирович : член-корреспондент РАН, доктор физико-математических н…»</p>
<hr />
<div>Якобовский Михаил Владимирович<br />
: член-корреспондент РАН, доктор физико-математических наук, профессор<br />
: зав. сектором ИПМ им. М.В. Келдыша РАН<br />
: профессор МФТИ, ФУПМ, кафедра Математического моделирования<br />
: профессор МГУ, ВМиК, кафедра Суперкомпьютеров и квантовой информатики<br />
: mailto:lira@imamod.ru</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:%D0%91%D0%BE%D1%80%D0%B8%D1%81&diff=20619Обсуждение участника:Борис2016-12-11T13:33:30Z<p>Lira: </p>
<hr />
<div>1.5 <br />
: строка 27 содержит ошибку<br />
<br />
1.7<br />
: Информационный граф должен отражать зависимости между операциями.<br />
представленный рисунок содержит горизонтальные ненаправленные дуги, не отражающие <br />
информационную зависимость на очередном шаге.<br />
<br />
: объём выходных данных указан не корректно. Вызвано это отсутствием точной постановки задачи.<br />
Промежуточные результаты часто не интересуют, интересуют значение <math>\textbf{f} </math> при <math>x=b</math> и, <br />
возможно, при некоторых промежуточных значениях, но не при всех.<br />
<br />
1.10<br />
: Утверждение "Устойчивость. Алгоритм устойчив на любом конечном отрезке." неверно, <br />
поскольку описанный метод, будучи явным, не является абсолютно устойчивым. <br />
Он устойчив лишь при достаточно малых значениях шага интегрирования.<br />
<br />
2.3, ..., 2.6<br />
Разделы отсутствуют.<br />
<br />
: [[Участник:Lira|Lira]] ([[Обсуждение участника:Lira|обсуждение]]) 16:33, 11 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:%D0%91%D0%BE%D1%80%D0%B8%D1%81&diff=20618Обсуждение участника:Борис2016-12-11T13:30:37Z<p>Lira: Новая страница: «1.5 : строка 27 содержит ошибку 1.7 : Информационный граф должен отражать зависимости между…»</p>
<hr />
<div>1.5 <br />
: строка 27 содержит ошибку<br />
<br />
1.7<br />
: Информационный граф должен отражать зависимости между операциями.<br />
представленный рисунок содержит горизонтальные ненаправленные дуги, не отражающие <br />
информационную зависимость на очередном шаге.<br />
<br />
: объём выходных данных указан не корректно. Вызвано это отсутствием точной постановки задачи.<br />
Промежуточные результаты часто не интересуют, интересуют значение <math>\textbf{f} </math> при <math>x=b</math> и, <br />
возможно, при некоторых промежуточных значениях, но не при всех.<br />
<br />
1.10<br />
: Утверждение "Устойчивость. Алгоритм устойчив на любом конечном отрезке." неверно, <br />
поскольку описанный метод, будучи явным, не является абсолютно устойчивым. <br />
Он устойчив лишь при достаточно малых значениях шага интегрирования.<br />
<br />
2.3, ..., 2.6<br />
Разделы отсутствуют.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Fokina&diff=20514Обсуждение участника:Fokina2016-12-10T09:45:11Z<p>Lira: /* Рекурсивная координатная бисекция */</p>
<hr />
<div>== Статья [[Участник:Fokina/Рекурсивная координатная бисекция]] ==<br />
<br />
=== Отсутствующие части ===<br />
* В теле статьи не указаны её авторы. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 27 октября 2016 (MSK)<br />
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:21, 16 ноября 2016 (MSK)<br />
<br />
=== Замечания по тексту ===<br />
* В разделе 1.5 кроме кода нужны текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 27 октября 2016 (MSK)<br />
* В разделе 2.4 не приведены все параметры запуска теста - какой компилятор, с какими опциями использовался, какие версии библиотек, на каких узлах проводился запуск и т.д. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:42, 23 ноября 2016 (MSK)<br />
<br />
== Рекурсивная координатная бисекция ==<br />
<br />
Разделы 1.1, 1.2<br />
"... протяженность разрезаемой области вдоль этой оси была наибольшей." <br />
: Неясно, в каких единицах измеряется протяженность. Масштаб по осям может быть весьма произвольным и указанный разрез может не отвечать требованию сокращения числа разрезанных рёбер.<br />
<br />
: Поправить окончания<br />
"обусловлено высокой скоростью работы метода, его простотА и ориентированнОСТЬ на распределенную обработку. " <br />
<br />
: Отсутствует логическая связь между первыми двумя и третьим предложением.<br />
: Третье предложение - это необходимое условие равномерного разбиения, к связности доменов оно не имеет отношения.<br />
<br />
"Наилучшие результаты метод демонстрирует на сетках, в которых вершины равномерно распределены по области простой формы. В других случаях могут возникать длинные границы с несвязанными поддоменами. Чтобы избежать этого, вместо деления доменов пополам на каждом этапе можно разбивать их таким образом, чтобы их размер был пропорционален итоговому количеству кластеров."<br />
<br />
<br />
Раздел 1.2<br />
: Непонятно, что такое n*k/2<br />
: Не определено n<br />
<br />
Раздел 1.3 <br />
: Текст "Параллельная версия данной сортировки также эффективна ..." неверен,<br />
поскольку указанная сложность имеет весьма косвенное отношение к пирамидальной сортировке. Это сложность сортировки Бетчера. Про битонную сортировку совсем неверно, поскольку её сложность определяется так же через число процессоров, а не через число узлов расчетной сетки. Более того, зависимость от n/p*log(n/p) в ней так же должна присутствовать. Указанные оценки справедливы не только в среднем, но и в худшем случае (а так же в лучшем).<br />
<br />
: [[Участник:lira|Якобовский Михаил Владимирович]] ([[Обсуждение участника:lira|обсуждение]]) 10:48, 10 декабря 2016 (MSK)<br />
<br />
: Последний комментарий в разделе 1.5 неверен (n1 != n*k/4)<br />
<br />
: Лучше поправить "не имеют информационных зависимостей друг между другом", заменив на "не имеют между собой информационных зависимостей"<br />
<br />
Раздел 1.8. <br />
: Утверждение "Исходя из того, что сложность этих подзадач примерно одинакова, можно считать, что их решение занимает примерно одинаковое время t и не зависит от яруса" неверно.<br />
Времена совпадают в пределах яруса, но, при параллельной обработке, они разные на разных ярусах, поскольку с увеличением номера яруса уменьшается объём обрабатываемых каждым процессором данных.<br />
Таким образом, ускорение определено неверно.<br />
<br />
Раздел 1.9. <br />
: "Поскольку метод не учитывает связи между вершинами ..." Такая стратегия применима только к ограниченному классу равномерных сеток. В случае сгущающихся сеток следует контролировать число разрезанных рёбер при разбиении вдоль каждой из осей, выбирая каждый раз наименьшее. Для этого необходимо хранить и использовать информацию о связях между вершинами. Как минимум следует обратить внимание вид обрабатываемых сеток.<br />
<br />
Раздел 1.10. <br />
: Откуда в первом абзаце оценка log(n)? Прокомментируйте. Оценка вычислительной сложности в параллельном случае тоже нуждается в проверке и комментариях. Сомнительно, что максимальное ускорение достигается на числе процессоров равном числу узлов расчетной сетки.<br />
<br />
Рисунки 3,4,7.<br />
: Подпись (производительность) не соответствует содержимому (время работы). <br />
<br />
Совершенно бессмысленно указывать эффективность с точностью до 12ой значащей цифры.<br />
<br />
Рисунок 7.<br />
: Судя по рисунку изменение числа процессоров от 4 до 128 никак не меняет времени счета. Ускорения нет. Какой смысл говорить о масштабируемости по данным?<br />
<br />
Раздел 2.7<br />
: Что известно о методе бисекции реализованном в ZOLTAN& Есть ли там вообще полная сортировка по осям? Является ли эта сортировка сортировкой Бетчера?<br />
<br />
<br />
<br />
: [[Участник:lira|Якобовский Михаил Владимирович]] ([[Обсуждение участника:lira|обсуждение]]) 13:00, 10 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Fokina/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%BA%D0%BE%D0%BE%D1%80%D0%B4%D0%B8%D0%BD%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%B1%D0%B8%D1%81%D0%B5%D0%BA%D1%86%D0%B8%D1%8F&diff=20509Обсуждение участника:Fokina/Рекурсивная координатная бисекция2016-12-10T07:51:38Z<p>Lira: Содержимое страницы заменено на «Замечания перенесены на страницу обсуждения участника: https://algowiki-project.org…»</p>
<hr />
<div>Замечания перенесены на страницу обсуждения участника:<br />
https://algowiki-project.org/ru/%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Fokina</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Fokina&diff=20508Обсуждение участника:Fokina2016-12-10T07:49:01Z<p>Lira: </p>
<hr />
<div>== Статья [[Участник:Fokina/Рекурсивная координатная бисекция]] ==<br />
<br />
=== Отсутствующие части ===<br />
* В теле статьи не указаны её авторы. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 27 октября 2016 (MSK)<br />
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:21, 16 ноября 2016 (MSK)<br />
<br />
=== Замечания по тексту ===<br />
* В разделе 1.5 кроме кода нужны текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 27 октября 2016 (MSK)<br />
* В разделе 2.4 не приведены все параметры запуска теста - какой компилятор, с какими опциями использовался, какие версии библиотек, на каких узлах проводился запуск и т.д. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:42, 23 ноября 2016 (MSK)<br />
<br />
== Рекурсивная координатная бисекция ==<br />
<br />
Разделы 1.1, 1.2<br />
"... протяженность разрезаемой области вдоль этой оси была наибольшей." <br />
: Неясно, в каких единицах измеряется протяженность. Масштаб по осям может быть весьма произвольным и указанный разрез может не отвечать требованию сокращения числа разрезанных рёбер.<br />
<br />
: Поправить окончания<br />
"обусловлено высокой скоростью работы метода, его простотА и ориентированнОСТЬ на распределенную обработку. " <br />
<br />
: Отсутствует логическая связь между первыми двумя и третьим предложением.<br />
: Третье предложение - это необходимое условие равномерного разбиения, к связности доменов оно не имеет отношения.<br />
<br />
"Наилучшие результаты метод демонстрирует на сетках, в которых вершины равномерно распределены по области простой формы. В других случаях могут возникать длинные границы с несвязанными поддоменами. Чтобы избежать этого, вместо деления доменов пополам на каждом этапе можно разбивать их таким образом, чтобы их размер был пропорционален итоговому количеству кластеров."<br />
<br />
<br />
Раздел 1.2<br />
: Непонятно, что такое n*k/2<br />
: Не определено n<br />
<br />
Раздел 1.3 <br />
: Текст "Параллельная версия данной сортировки также эффективна ..." неверен,<br />
поскольку указанная сложность имеет весьма косвенное отношение к пирамидальной сортировке. Это сложность сортировки Бетчера. Про битонную сортировку совсем неверно, поскольку её сложность определяется так же через число процессоров, а не через число узлов расчетной сетки. Более того, зависимость от n/p*log(n/p) в ней так же должна присутствовать. Указанные оценки справедливы не только в среднем, но и в худшем случае (а так же в лучшем).<br />
[[Участник:lira|Якобовский Михаил Владимирович]] ([[Обсуждение участника:lira|обсуждение]]) 10:48, 10 декабря 2016 (MSK)</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Fokina&diff=20507Обсуждение участника:Fokina2016-12-10T07:40:24Z<p>Lira: /* Рекурсивная координатная бисекция */ новая тема</p>
<hr />
<div>== Статья [[Участник:Fokina/Рекурсивная координатная бисекция]] ==<br />
<br />
=== Отсутствующие части ===<br />
* В теле статьи не указаны её авторы. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 27 октября 2016 (MSK)<br />
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:21, 16 ноября 2016 (MSK)<br />
<br />
=== Замечания по тексту ===<br />
* В разделе 1.5 кроме кода нужны текстовые пояснения. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 17:10, 27 октября 2016 (MSK)<br />
* В разделе 2.4 не приведены все параметры запуска теста - какой компилятор, с какими опциями использовался, какие версии библиотек, на каких узлах проводился запуск и т.д. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:42, 23 ноября 2016 (MSK)<br />
<br />
== Рекурсивная координатная бисекция ==<br />
<br />
Разделы 1.1, 1.2<br />
"... протяженность разрезаемой области вдоль этой оси была наибольшей." <br />
: Неясно, в каких единицах измеряется протяженность. Масштаб по осям может быть весьма произвольным и указанный разрез может не отвечать требованию сокращения числа разрезанных рёбер.<br />
<br />
: Поправить окончания<br />
"обусловлено высокой скоростью работы метода, его простотА и ориентированнОСТЬ на распределенную обработку. " <br />
<br />
: Отсутствует логическая связь между первыми двумя и третьим предложением.<br />
: Третье предложение - это необходимое условие равномерного разбиения, к связности доменов оно не имеет отношения.<br />
<br />
"Наилучшие результаты метод демонстрирует на сетках, в которых вершины равномерно распределены по области простой формы. В других случаях могут возникать длинные границы с несвязанными поддоменами. Чтобы избежать этого, вместо деления доменов пополам на каждом этапе можно разбивать их таким образом, чтобы их размер был пропорционален итоговому количеству кластеров."<br />
<br />
<br />
Раздел 1.2<br />
: Непонятно, что такое n*k/2<br />
: Не определено n<br />
<br />
Раздел 1.3 <br />
: Текст "Параллельная версия данной сортировки также эффективна ..." неверен,<br />
поскольку указанная сложность имеет весьма косвенное отношение к пирамидальной сортировке. Это сложность сортировки Бетчера. Про битонную сортировку совсем неверно, поскольку её сложность определяется так же через число процессоров, а не через число узлов расчетной сетки. Более того, зависимость от n/p*log(n/p) в ней так же должна присутствовать. Указанные оценки справедливы не только в среднем, но и в худшем случае (а так же в лучшем).</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%9E%D0%B1%D1%81%D1%83%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5_%D1%83%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA%D0%B0:Fokina/%D0%A0%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D0%BA%D0%BE%D0%BE%D1%80%D0%B4%D0%B8%D0%BD%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%B1%D0%B8%D1%81%D0%B5%D0%BA%D1%86%D0%B8%D1%8F&diff=20504Обсуждение участника:Fokina/Рекурсивная координатная бисекция2016-12-09T23:15:32Z<p>Lira: Новая страница: «Разделы 1.1, 1.2 "... протяженность разрезаемой области вдоль этой оси была наибольшей." : Нея…»</p>
<hr />
<div>Разделы 1.1, 1.2<br />
"... протяженность разрезаемой области вдоль этой оси была наибольшей." <br />
: Неясно, в каких единицах измеряется протяженность. Масштаб по осям может быть весьма произвольным и указанный разрез может и не отвечать требованию сокращения числа разрезанных рёбер.<br />
<br />
: Поправить окончания<br />
"обусловлено высокой скоростью работы метода, его простотА и ориентированнОСТЬ на распределенную обработку. " <br />
<br />
: Отсутствует логическая связь между первыми двумя и третьим предложением.<br />
: Третье предложение - это необходимое условие равномерного разбиения, к связности доменов оно не имеет отношения.<br />
<br />
Наилучшие результаты метод демонстрирует на сетках, в которых вершины равномерно распределены по области простой формы. В других случаях могут возникать длинные границы с несвязанными поддоменами. Чтобы избежать этого, вместо деления доменов пополам на каждом этапе можно разбивать их таким образом, чтобы их размер был пропорционален итоговому количеству кластеров.<br />
<br />
<br />
Раздел 1.2<br />
: Непонятно, что такое n*k/2<br />
: Не определено n<br />
<br />
Раздел 1.3 <br />
: Текст "Параллельная версия данной сортировки также эффективна ..." неверен,<br />
поскольку указанная сложность имеет весьма косвенное отношение к пирамидальной сортировке. Это сложность сортировки Бетчера. Про битонную сортировку совсем неверно, поскольку её сложность определяется так же через число процессоров, а не через число узлов расчетной сетки. Более того, зависимость от n/p*log(n/p) в ней так же должна присутствовать. Указанные оценки справедливы не только в среднем, но и в худшем случае (а так же в лучшем).</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D1%8C_%D0%BD%D0%B5%D1%87%D0%B5%D1%82%D0%BD%D0%BE-%D1%87%D0%B5%D1%82%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8&diff=998Сеть нечетно-четной перестановки2015-03-01T22:50:00Z<p>Lira: Новая страница: «Сеть нечетно-четной перестановки»</p>
<hr />
<div>Сеть нечетно-четной перестановки</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=997Сети сортировки2015-03-01T22:46:11Z<p>Lira: /* Словесное описание алгоритма */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее согласованную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны, с точки зрения последовательного выполнения, но обеспечивают эффективную параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для некоторого фиксированного числа элементов.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть нечетно-четной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 элементов[1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i<j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
==== Временные материалы (в таком виде их не следует включать) ====<br />
<br />
Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%BE%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2&diff=996Список описаний алгоритмов2015-03-01T22:36:47Z<p>Lira: </p>
<hr />
<div># * [[Разложение Холецкого (метод квадратного корня)]] [[file:pr_checked-05.png]] [[file:pr_checked-06.png]]<br />
# * [[Суммирование сдваиванием]]<br />
# [[Равномерная норма вектора, вещественная версия, последовательный вариант]]<br />
# * [[Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант]]<br />
# [[Скалярное произведение векторов, вещественная версия, последовательный вариант]]<br />
# * [[Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]]<br />
# * [[High Performance Conjugate Gradient (HPCG) benchmark]]<br />
# * [[Linpack benchmark]]<br />
# [[Сумма вектора и произведения матрицы на другой вектор, вещественная версия, последовательный вариант, плотная матрица]]<br />
# [[Сумма вектора и произведения матрицы на другой вектор, вещественная версия, последовательный вариант, разрежённая матрица]]<br />
# * [[Последовательно-параллельный метод суммирования]]<br />
# [[Последовательно-параллельный метод нахождения всех частных выражений для ассоциативных операций]]<br />
# [[Схема Горнера, вещественная версия, последовательный вариант]]<br />
# [[Сдвиг аргументов многочлена по схеме Горнера, вещественная версия, последовательный вариант]]<br />
# [[Решение правой двухдиагональной СЛАУ, вещественная версия, последовательный вариант]]<br />
# [[Решение правой двухдиагональной СЛАУ с единичной диагональю, вещественная версия, последовательный вариант]]<br />
# [[Решение левой двухдиагональной СЛАУ, вещественная версия, последовательный вариант]]<br />
# [[Решение левой двухдиагональной СЛАУ с единичной диагональю, вещественная версия, последовательный вариант]]<br />
# [[Разложение трёхдиагональной матрицы, вещественная версия, последовательный вариант (первая стадия прогонки)]]<br />
# [[Разложение трёхдиагональной матрицы, вещественная версия, последовательный вариант без корней (первая стадия прогонки)]]<br />
# [[Разложение трёхдиагональной матрицы, вещественная версия, последовательный вариант с корнями (первая стадия прогонки)]]<br />
# * [[Быстрое преобразование Фурье для степеней двойки]]<br />
# * [[Умножение плотных матриц]]<br />
# * [[Умножение плотной матрицы на вектор]]<br />
# * [[Метод Гаусса решения СЛАУ (прямой ход)]]<br />
# * [[Метод Гаусса решения СЛАУ (обратный ход)]]<br />
# * [[Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)]]</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D1%8C_%D1%87%D0%B5%D1%82%D0%BD%D0%BE-%D0%BD%D0%B5%D1%87%D0%B5%D1%82%D0%BD%D0%BE%D0%B9_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=995Сеть четно-нечетной сортировки2015-03-01T22:36:10Z<p>Lira: Новая страница: «Сеть четно-нечетной сортировки»</p>
<hr />
<div>Сеть четно-нечетной сортировки</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%BE%D0%BF%D0%B8%D1%81%D0%B0%D0%BD%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2&diff=994Список описаний алгоритмов2015-03-01T22:36:00Z<p>Lira: </p>
<hr />
<div># * [[Разложение Холецкого (метод квадратного корня)]] [[file:pr_checked-05.png]] [[file:pr_checked-06.png]]<br />
# * [[Суммирование сдваиванием]]<br />
# [[Равномерная норма вектора, вещественная версия, последовательный вариант]]<br />
# * [[Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант]]<br />
# [[Скалярное произведение векторов, вещественная версия, последовательный вариант]]<br />
# * [[Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант]]<br />
# * [[High Performance Conjugate Gradient (HPCG) benchmark]]<br />
# * [[Linpack benchmark]]<br />
# [[Сумма вектора и произведения матрицы на другой вектор, вещественная версия, последовательный вариант, плотная матрица]]<br />
# [[Сумма вектора и произведения матрицы на другой вектор, вещественная версия, последовательный вариант, разрежённая матрица]]<br />
# * [[Последовательно-параллельный метод суммирования]]<br />
# [[Последовательно-параллельный метод нахождения всех частных выражений для ассоциативных операций]]<br />
# [[Схема Горнера, вещественная версия, последовательный вариант]]<br />
# [[Сдвиг аргументов многочлена по схеме Горнера, вещественная версия, последовательный вариант]]<br />
# [[Решение правой двухдиагональной СЛАУ, вещественная версия, последовательный вариант]]<br />
# [[Решение правой двухдиагональной СЛАУ с единичной диагональю, вещественная версия, последовательный вариант]]<br />
# [[Решение левой двухдиагональной СЛАУ, вещественная версия, последовательный вариант]]<br />
# [[Решение левой двухдиагональной СЛАУ с единичной диагональю, вещественная версия, последовательный вариант]]<br />
# [[Разложение трёхдиагональной матрицы, вещественная версия, последовательный вариант (первая стадия прогонки)]]<br />
# [[Разложение трёхдиагональной матрицы, вещественная версия, последовательный вариант без корней (первая стадия прогонки)]]<br />
# [[Разложение трёхдиагональной матрицы, вещественная версия, последовательный вариант с корнями (первая стадия прогонки)]]<br />
# * [[Быстрое преобразование Фурье для степеней двойки]]<br />
# * [[Умножение плотных матриц]]<br />
# * [[Умножение плотной матрицы на вектор]]<br />
# * [[Метод Гаусса решения СЛАУ (прямой ход)]]<br />
# * [[Метод Гаусса решения СЛАУ (обратный ход)]]<br />
# * [[Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)]]<br />
# [[Сеть четно-нечетной сортировки]]</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=993Сети сортировки2015-03-01T21:49:18Z<p>Lira: /* Временные материалы (в таком виде их не следует включать) */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i<j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
==== Временные материалы (в таком виде их не следует включать) ====<br />
<br />
Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=992Сети сортировки2015-03-01T19:40:54Z<p>Lira: /* Математическое описание */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>A</math>, содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i<j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
==== Временные материалы (в таком виде их не следует включать) ====<br />
<br />
Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=974Сети сортировки2015-02-23T21:21:45Z<p>Lira: </p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>A</math> содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i<j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
==== Временные материалы (в таком виде их не следует включать) ====<br />
<br />
Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=973Сети сортировки2015-02-23T21:19:44Z<p>Lira: /* Описание свойств и структуры алгоритма */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>A</math> содержащий <math>n</math> элементов, <math>|A|=n</math>.<br />
<br />
Вычисляемые данные: упорядоченный массив <math>B=sort(A)</math>.<br />
<br />
==== Постановка задачи ====<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Без ограничения общности рассмотрим задачу расположения <math>n</math> элементов массива в порядке неубывания.<br />
Пусть <math>B^i</math> – <math>i</math>-ый элемент массива <math>B</math>. <br />
Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki><br />
<br />
<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i<j</math>.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>. <br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент <math>i</math>-го фрагмента массива <math>B</math> (фрагмента, расположенного на процессоре <math>i</math>). <br />
<br />
Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
==== Дополнительные замечания ====<br />
<br />
Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. <br />
Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=972Сети сортировки2015-02-23T20:57:59Z<p>Lira: /* Дополнительные замечания */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
Постановка задачи.<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. По окончании сортировки элементы исходного массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>, каждая из которых упорядочена. Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент фрагмента массива <math>B_i</math>, расположенного на процессоре <math>i</math>. <br />
<br />
Массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
==== Дополнительные замечания ====<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
Для упрощения изложения далее рассматривается задача расположения в порядке неубывания <math>n</math> элементов массива целых <math>32</math>-разрядных чисел.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=971Сети сортировки2015-02-23T20:57:37Z<p>Lira: /* Математическое описание */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
Постановка задачи.<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
<br />
Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. По окончании сортировки элементы исходного массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>, каждая из которых упорядочена. Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент фрагмента массива <math>B_i</math>, расположенного на процессоре <math>i</math>. <br />
<br />
Массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
=== Дополнительные замечания ===<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
Для упрощения изложения далее рассматривается задача расположения в порядке неубывания <math>n</math> элементов массива целых <math>32</math>-разрядных чисел.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=970Сети сортировки2015-02-23T20:44:16Z<p>Lira: /* Математическое описание */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
Постановка задачи.<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
Для упрощения изложения далее рассматривается задача расположения в порядке неубывания <math>n</math> элементов массива целых <math>32</math>-разрядных чисел. Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом. Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. По окончании сортировки элементы исходного массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>, каждая из которых упорядочена. Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент фрагмента массива <math>B_i</math>, расположенного на процессоре <math>i</math>. <br />
<br />
Массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=969Сети сортировки2015-02-23T20:11:06Z<p>Lira: /* Математическое описание */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
Постановка задачи.<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
Для упрощения изложения далее рассматривается задача расположения в порядке неубывания <math>n</math> элементов массива целых <math>32</math>-разрядных чисел. Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом. Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>. По окончании сортировки элементы исходного массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>, каждая из которых упорядочена. Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.<br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент фрагмента массива <math>B_i</math>, расположенного на процессоре <math>i</math>. <br />
<br />
Массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki><br />
<br />
<math>B_i^k<=B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,<br />
<br />
<math>B_i^k<=B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=968Сети сортировки2015-02-23T19:47:08Z<p>Lira: /* Математическое описание */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
Постановка задачи.<br />
''Сортировкой'', или упорядочиванием элементов, называется процесс их расположения согласно определенному линейному отношению порядка, такому как отношение «меньше или равно» для чисел.<br />
Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.<br />
<br />
Для упрощения изложения далее рассматривается задача расположения в порядке неубывания <math>n</math> элементов массива целых <math>32</math>-разрядных чисел. Если не оговорено иное, будем считать, что сортировка выполняется на вычислительной системе с распределенной памятью. Данное предположение, благодаря потенциальной возможности обработки произвольно большого набора данных, существенно расширяет область применимости рассматриваемых методов.<br />
<br />
Уточним, что будет пониматься под упорядоченным массивом. Будем предполагать, что исходный массив распределен по процессорам некоторыми порциями <math>Ai</math>, где <math>i</math> – номер процессора. По окончании сортировки элементы исходного массива распределены по процессорам некоторыми порциями <math>B_i</math>, каждая из которых упорядочена. Потребуем, чтобы размеры всех порций были одинаковы. Как будет показано, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, могут быть использованы для сортировки массивов. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки. Таким образом, далее полагаем, что размеры исходных и отсортированных порций совпадают между собой: <math>|A_i|=|B_i|</math>.<br />
<br />
Пусть <math>B_i^k</math> – <math>k</math>-ый элемент фрагмента массива <math>B_i</math>, расположенного на процессоре <math>i</math>. Массив B упорядочен, если выполняются следующие соотношения:<br />
<math>B_i^k<=B_i^j</math> , для любых <math>i</math>, при <math>k<j</math><br />
<br />
<math>B_i^k<=B_l^j</math> , для любых <math>i,j</math>, при <math>i<l</math>.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=967Сети сортировки2015-02-23T18:51:03Z<p>Lira: /* Словесное описание алгоритма */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для параллельной сортировки больших объемов данных. Каждая сеть сортировки задаёт <br />
расписание, обеспечивающее безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить сети сортировки, правила создания которых известны для произвольного числа процессоров, и сети, известные только для массивов некоторых фиксированных размеров.<br />
<br />
К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных]], с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=833Сети сортировки2014-12-08T21:39:51Z<p>Lira: </p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для быстрой сортировки больших объёмов данных. Их основное преимущество заключается в предоставлении жёсткого расписания, обеспечивающего параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и немасштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных с точки зрения времени выполнения]] сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=832Сети сортировки2014-12-07T11:46:36Z<p>Lira: /* Словесное описание алгоритма */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для быстрой сортировки больших объёмов данных. Их основное преимущество заключается в предоставлении жёсткого расписания, обеспечивающего бесконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и немасштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных с точки зрения времени выполнения]] сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=831Сети сортировки2014-12-07T11:43:40Z<p>Lira: /* Словесное описание алгоритма */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для быстрой сортировки больших объёмов данных. ''Несогласованность по числам. Было: сети используЕтся в качестве алгоритма... Их преимущество...'' Их основное преимущество заключается в предоставлении жёсткого расписания, обеспечивающего бесконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и немасштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных с точки зрения времени выполнения]] сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=830Сети сортировки2014-12-07T11:43:00Z<p>Lira: /* Словесное описание алгоритма */</p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используются для быстрой сортировки больших объёмов данных. //Несогласованность по числам. Было: сети используЕтся в качестве алгоритма... Их преимущество...// Их основное преимущество заключается в предоставлении жёсткого расписания, обеспечивающего бесконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и немасштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных с точки зрения времени выполнения]] сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A4%D0%B0%D0%B9%D0%BB:Sort01.png&diff=829Файл:Sort01.png2014-12-07T11:33:23Z<p>Lira: Lira загружена новая версия «Файл:Sort01.png»</p>
<hr />
<div>Профиль доступа к памяти. n=128. Сортировка Бетчера</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=828Сети сортировки2014-12-07T01:39:33Z<p>Lira: </p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и немасштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных с точки зрения времени выполнения]] сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.<br />
# Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.</div>Lirahttps://algowiki-project.org/w/ru/index.php?title=%D0%A1%D0%B5%D1%82%D0%B8_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8&diff=827Сети сортировки2014-12-07T01:37:47Z<p>Lira: </p>
<hr />
<div>== Описание свойств и структуры алгоритма ==<br />
=== Словесное описание алгоритма ===<br />
<br />
'''Сети сортировки''' используется в качестве быстрого алгоритма сортировки больших объемов данных. Их основное преимущество заключается в предоставлении жесткого расписания, обеспечивающего безконфликтную параллельную работу нескольких процессоров над общей задачей упорядочивания множества элементов массива. Сети сортировки неэффективны с точки зрения последовательного выполнения, но обеспечивают быструю параллельную сортировку. Можно выделить масштабируемые и немасштабируемые сети сортировки. К первым следует отнести [[сеть сортировки простой вставкой]], [[сеть четно-нечетной перестановки]], [[сеть четно-нечетного слияния Бетчера]] и [[сеть битонной сортировки]]. К немасштабируемым следует отнести ряд [[оптимальные сети сортировки| оптимальных с точки зрения времени выполнения]] сетей для 6, 9, 10, 12 и 16 процессоров [1].<br />
<br />
=== Математическое описание ===<br />
<br />
Исходные данные: одномерный массив <math>n</math> чисел.<br />
<br />
Вычисляемые данные: упорядоченный массив.<br />
<br />
=== Вычислительное ядро алгоритма ===<br />
=== Описание схемы реализации последовательного алгоритма ===<br />
=== Последовательная сложность алгоритма ===<br />
=== Информационный граф ===<br />
=== Описание ресурса параллелизма алгоритма ===<br />
=== Описание входных и выходных данных ===<br />
=== Свойства алгоритма ===<br />
== Программная реализация ==<br />
=== Особенности реализации последовательного алгоритма ===<br />
=== Описание локальности данных и вычислений ===<br />
==== Описание локальности алгоритма ====<br />
==== Описание локальности реализации алгоритма ====<br />
===== Описание структуры обращений в память и качественная оценка локальности =====<br />
[[Файл:Sort01.png|thumb|center|1110px|Профиль доступа к памяти]]<br />
<br />
<br />
===== Количественная оценка локальности =====<br />
=== Возможные способы и особенности реализации параллельного алгоритма ===<br />
=== Масштабируемость алгоритма и его реализации ===<br />
==== Описание масштабируемости алгоритма ====<br />
==== Описание масштабируемости реализации алгоритма ====<br />
=== Динамические характеристики и эффективность реализации алгоритма ===<br />
=== Выводы для классов архитектур ===<br />
=== Существующие реализации алгоритма ===<br />
== Литература ==<br />
# Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.</div>Lira