Автор неизвестен - Бионика интелекта информация язык интеллект№ 3 (77) 2011научно-технический журналоснован в октябре 1967 г - страница 61

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 

3. Упорядочение элементов

С учётом введенного понятия меры разупоря-доченности, может быть показано, что множества, упорядоченные по возрастанию и убыванию, вза­имно максимально разупорядочены по отноше­нию друг к другу. В частности, для данного мно­жества число перестановок в парах соседствующих элементов является максимальным при переупо­рядочении множества из упорядоченности по воз­растанию в упорядоченность по убыванию, или наоборот: (2) — (3) или (3) — (2)

Графы, представленные на рис. 1 а, б иллюстри­руют сказанное для множеств из трёх и четырёх разных элементов. Термин «разный» понимается в значении a,, ф aj; a,, aj є A; i, j є (1, 2, 3,..., я); iф j.

б

Рис. 1. Структуры частично упорядоченных множеств перестановок трёхэлементной (а) и четырёхэлементной ( б) последовательностей.

При рассмотрении цепочек перестановок необ­ходимо исключить циклы, ограничившись только продуктивными перестановками. Графы рис. 1 а, б позволяют проследить различные варианты таких цепочек, поскольку охватывают все возможные варианты связей по перестановкам в парах сосед­ствующих элементов. Так, для 4-элементной по­следовательности (рис. 1 б) одна из цепочек преоб­разования (1, 2, 3, 4) — (4, 3, 2, 1) имеет следующий вид:

Г1 Г1

(1, 2, 3, 4)   —   (2, 1, 3, 4) —

— (2, 1, 4, 3)   —   (2, 4, 1, 3)   — (4)

Г1 -ГТ-

— (4, 2, 1, 3)   —   (4, 2, 3, 1) —

— (4, 3, 2, 1)

В (4) любые две соседние последовательности, раз­делённые знаком « — », различаются перестановкой местами одной (обозначенной) пары двух соседних элементов (цифр). Другая соседствующая пара, если она имеется и может быть переставлена, тем не ме­нее остаётся незадействованной, поскольку проце­дура сортировки последовательная. В результате, (1, 2, 3, 4) — (4, 3, 2, 1) реализуется за 6 шагов. Эта ситуация имеет место не только для (4), но и для любых вариантов цепочек перестановки элементов, что может быть прослежено непосредственно по графу (рис. 1 б), на котором имеется 7 вертикальных столбцов расположения 4-элементных последова­тельностей, различающихся перестановкой одной пары элементов.

В отличие от последовательной процедуры со­ртировки, ЛП процедура поддерживает обмен местами сразу нескольких (всех имеющихся) пар соседствующих элементов последовательности. Вследствие этого, как будет показано далее, чис­ло переходов « — » в процедуре сортировки может быть существенно сокращено.

4. Локальная параллельность

ЛП обработка информации на процессорах общего назначения допускает широкий круг при­ложений. Принцип ЛП обработки информации может быть проиллюстрирован на следующем вы­числительным примером. Имеется n выражений ci = ai + b{; i = 1, 2,..., я. Значения a, и bi заданы. Требуется найти значения е.. Если используется ВС с одним процессором, задача разрешима за 4я шагов: загрузить ai, загрузить bi, произвести сум­мирование, выгрузить результат ci. Если ai и bi по­ложительные, имеют ограниченное число разрядов и если в результате сложении разрядность не нару­шается (числа ai, bi и ci имеют одинаковую разряд­ность), исходные данные могут быть представлены в виде:

A = аг © a2 © ... © a © ... © an;

B = b1 © b2 © ... © b © ... © Ья, (5)

где символом © обозначена конкатенация. Если разрядность результата превышает разрядность слагаемых для переноса избыточного разряда при суммировании в формате представления данных требуется предусмотреть разделительные нули. В обоих случаях результат C = A + B может быть интерпретирован как конкатенация аналогично (5), в которой сегменты числа ci соответствуют

Мохамад Али, О. Ф. Михаль

по формату at и b При этом весь набор значений ct может быть получен за 4 шага. Здесь я-кратный выи­грыш достигнут без учёта «окаймляющих» операций конкатенации-деконкатенации, предназначенных для формирования A и B и извлечения результатов ct из C. Если в реальном случае вычислительный блок достаточно сложный и включает последовательное применение нескольких разнообразных операций без промежуточных конкатенаций-деконкатенаций, выигрыш может быть значительным. Выигрыш растёт с ростом разрядности процессора и с сокра­щением размеров конкатенируемых сегментов. При этом снижается точность представления данных (система «загрубляется»), что в ряде конкретных приложений бывает допустимо.

Рост разрядности процессоров является долго­временной устойчивой тенденцией развития про­цессорной техники. Известный закон Мура об удвоении числа транзисторов на кристалле на практике означает удвоение разрядности реги­стров процессора. Разрядность регистров, как из­вестно, это объём непосредственно адресуемой оперативной памяти, т.е. допустимая размерность задач, разрешимых в данном ВС за приемлемое время. Поэтому разрядность вероятно, будет на­ращиваться и в дальнейшем, поскольку при этом стимулируется появление новых вычислительных задач, которые в свою очередь стимулируют рост требований к техническим характеристикам вновь разрабатываемых ВС. Данная «обратная связь» ис­правно работает на протяжении всей истории раз­вития ВС и нет причин предполагать отход от дан­ной тенденции. Соответственно, есть основания прогнозировать рост эффективности (произво­дительности) применения ЛП алгоритмов за счёт увеличения числа конкатенируемых сегментов.

5. ЛП сортировка

Проиллюстрируем работу алгоритма ЛП сорти­ровки ОМНД следующим образом. Пусть имеется множество элементов, на котором определено от­ношение порядка:

A: {a1, a2, a3, a4,..., an}; a1 > a2 > a3 > a4 >...> an. (6)

Пусть из элементов множества А составлена разупорядоченная последовательность:

B: (Ья, b(„-1),..., b2, b1), bt = aj, 2,..., я},

3 (i, j): i фj. (7)

В частности, в максимально разупорядоченном случае (7) может быть обратно упорядоченным на­бором элементов из (6): B: (an an-1, an_2, an_3, an-4,...,

a3, a2, a1).

Требуется упорядочить последовательность (7) в порядке убывания величины элементов от млад­шего (правого) к старшему (левому), т.е. привести к упорядочению согласно (6).

Производим конкатенацию (5) элементов bt со­гласно их расположению в последовательности (7). Далее в вербальном описании ЛП процедура со­ртировки включает следующие 4 шага.

Шаг 1. Скопировать текущее В для последую­щего сравнения: B1=B.

Шаг 2. Сравнить попарно нечётные элементы B с чётными, стоящими слева от них. В каждой срав­ниваемой паре больший из элементов поставить на нечётное место, а меньший на чётное.

Шаг 3. Сравнить попарно чётные элементы B с нечётными, стоящими слева от них. В каждой срав­ниваемой паре больший из элементов поставить на чётное место, а меньший — на нечётное.

Шаг 4. Сравнить В и В1. Если B1=B, ЛП проце­дура сортировки закончена. Результат содержится в В. Если B1 ф B перейти к Шагу.1.

Процедура иллюстрируется рисунком 2. Разделе -ние сегментов на чётные и нечётные организовано посредством пары регистров R1 и R2. Заштрихова­ны фрагменты регистров, в которых расположены информационные сегменты. Разделение (проре­живание) конкатенации вида (4) на четный (R2) и нечётный (R1) регистры программно реализуется применением процедуры побитового «И» с исполь­зованием пары битовых полумасок вида:

£1:{...(11...1)(00...0)(11...1)(00...0)(11...1)};

Е2:{.400..Ю)(11.Л)(00..Ю)(11...1)(00...0)}. (8)

Сегменты, соответствующие конкатенирован­ным данным в (5), выделены в (8) круглыми скоб­ками.

яіУА  У/Л  УЛ Ч7> яг У Л У Л УЛ~ Я1УА  У/Л  УЛ 77>

г д о

яг У Л  У/Л  kXI МУА  Ш   УЛ U) ягУА  УЛ У/Г яіУА  Ш  УЛ У7> Я2УА  У/Л У А I

Рис. 2. Работа ЛП алгоритма сортировки

Регистры последовательно совмещаются для со­поставления (Шаги 2 и 3) применением регистро­вых сдвигов на число бит, равное длине сегмента. Посегментное сопоставление показано двунаправ­ленными прозрачными стрелками. Однонаправ­ленные прозрачные стрелки показывают общеепрохождение ЛП процедуры по Шагам 1 — 4. За­грузка исходных данных и вывод результата обо­значены in и out.

6. Чередование обменов

Основные черты ЛП сортировки ОМНД соглас­но алгоритму (рис. 2) могут быть прослежены на примере пересортировки набора из 8 элементов:

(7, 6, 5, 4, 3, 2, 1, 0) — (0, 1, 2, 3, 4, 5, 6, 7). (9)

Соответствующая процедура представлен на рис. 3.

Существенным (и тривиальным) ограничени­ем при выполнении обычной (не ЛП) процедуры сортировки является последовательньгй характер выполнения действий. Как отмечалось, в каждом акте сопоставления рассматривается исключитель­но одна пара соседствующих элементов (ai, Предшествующие (a1, a2), (a2, a3),..., (ai-1, a) и по­следующие a,+2), (a+2, a+3),..., (an-1, an) пары остаются вне рассмотрения. Таким образом про-делывается n-1 однократных операций сопостав­ления. При этом, когда одна пара сопоставляется, n-2 не задействованы. Введением ЛП обработки эффективность существенно повышается: парал­лельно проводится ещё до (n/2)-1 сопоставлений.

Нумерация шагов процесса дана в левой колон­ке. Нижняя строка — результат сортировки, полу­ченный после ЛП операций обмена в предпослед­ней строке.

Страницы:
1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  75  76  77 


Похожие статьи

Автор неизвестен - 13 самых важных уроков библии

Автор неизвестен - Беседы на книгу бытие

Автор неизвестен - Беседы на шестоднев

Автор неизвестен - Богословие

Автор неизвестен - Божественность христа