СТРОКА ОБРАЩЕНИЙК, СТРАНИЦАМ ДЛЯ ПРОГРАММЫ, ЗАНИМАЮЩЕЙ 20 СТР,НИЦ

СТРАНИЦЫ 1 ... 6 ЙАНЯТЫ ТЕКСТОМ ПРОГРАММЫ СТРАНИЦЫ 7. . . 20 ЗАНЯТЫ ДАННЫМИ

Рис. 5.4.6. Цепочка обращений к страницам для программы с 20 страницами; страницы с 1 по 6 - текст программы, а страницы с 7 по 20 - данные.

5.4.2. Реализуйте алгоритм RANDOM.

5.4.3. Реализуйте алгоритм BEST.

5.4.4. Алгоритмы управления страничной памятью (проверка). Ради простоты и краткости обсуждения мы сделали ряд упрощающих предположений. Оцените критически эти предположения и процедуры проверки, которым мы следовали в этой главе.

L5.4.5. Алгоритмы управления страничной памятью (проверка). Исследуйте процедуры управления страничной памятью (если таковые существуют), применяемые на вашей ЭВМ.

L5.4.6. Алгоритмы управления страничной памятью (проверка). Алгоритмы управления страничной памятью, рассмотренные в данном разделе, проверены недостаточно тщательно. Подкрепите проведенное обсуждение собственными экспериментами.

5.5. Параллелиз.м

За последние 30 лет развития вычислительной техники были сделаны поистине впечатляющие достижения в областях скорости, размера и сложности компьютеров. Начав с компьютеров, обладавших памятью 8К слов и с миллисекундным циклом (10"? с), мы пришли

1.00 г

0.30 -

t.20 -

Чаетото отказов

о Аогоритм RANDOM X Алгоритм FIFO d Алгоритм LRU

• Алгоритм LFU

* Алгоритм BEST

О.ОО 2.00 4.00 6.00 Е.00 IC.OQ 12.00 М.ОО I6.D0 18.00

Число cmpoKui; 6 mmmji

Рис. 5.4.7. Результаты испытания пяти алгоритмов управления страничной памятью.

К таким компьютерам, как ИЛЛИАК IV, обладающий памятью в 512К 64-битовых слов и циклом 240 не {не = Ю"» с). В основном повышение производительности больших машин за прошедшие годы было достигнуто за счет прогрессивных компонентов, в особенности за счет микроминиатюризации электронных схем.

Однако при наблюдаемом повсюду ненасытном аппетите в отношении все больших и более быстрых компьютеров мы, по-видимому, подходим к технологическому тупику, который воспрепятствует значительным достижениям в будущем. Скорости сегодняшних компьютеров фактически ограничены из-за физической длины проводов, которые используются для передачи данных.

Одним из многообещающих путей обхода ограничения скорости из-за времени передачи данных является перестройка вычислительных систем на параллельное выполнение большего числа операций. Эта идея привела к развитию многопроцессорных систем, структурированных процессоров для обработки массивов, неструктурированных машин для обработки линейных массивов, ассоциативных процессоров и конвейерных процессоров. Это все различные виды параллельных машин.

Укажем на нескольких примерах, как можно использовать параллелизм для ускорения вычислений:

1. Одновременное выполнение операций ввода/вывода и вьислений в программе.

2. Присвоение нулевого значения всем элементам массива.

3. Арифметическая обработка вектора или массива, например А

fiJ-C, где В и С - векторы или матрицы (эта возможность уже реализована в таких языках, как APL).

4. Одновременное отслеживание ветвей и границ в различных узлах древовидной структуры.

5. Выполнение одинаковых последовательностей операций над различными множествами данных.

6. Выполнение различных и независимых операций над одним и тем же множеством данных.

7. Конвейерная обработка, или предвидение, т. е. одновременная обработка различных команд в последовательном списке команд, когда эти команды находятся на различных стадиях выполнения.

8. Выполнение одновременного поиска.

9. Параллельная сортировка.

10. Выполнение одновременных функциональных преобразований, например, при поиске максимума или нуля функции.

Мы не собираемся утверждать, что все вычисления можно «сделать» параллельными. В этой связи, по-видимому, за краткую историю параллельных вычислений выработалось эмпирическое правило, называемое эффектом Амдаля. Грубо говоря, оно гласит, что для достаточной эффективности вычислений на параллельной машине с т процессорами вычисления должны распадаться на т потоков данных, причем нужно, чтобы последовательно выполнялась существенно меньшая, чем 1/т, доля сегментов. Эффект Амдаля основан на отсутствии внртреннего параллелизма в большинстве современных программ. Хотя реальный мир сам по себе «параллелен», наш алгоритмический подход к нему в своей основе последовательный. Отчасти это объясняется более чем тремя столетиями последовательной математики и более чем двумя десятилетиями последовательного программирования на Фортране.

Параллельный алгоритм отыскания остовного дерева

Давайте начнем с некоторых интуитивных представлений, необходимых для разработки и анализа параллельных алгоритмов. Вернемся к алгоритму построения остовного дерева минимального веса из гл. 4. Можно попытаться построить параллельную версию этого алгоритма, рассмотрев, что произошло бы, если бы мы одновременно выбрали по ребру с наименьшим весом, инцидентному каждой вершине во взвешенной сети G,