Раздел: Документация
0 ... 63 64 65 66 67 68 69 ... 78 сор размером 128X128 МРР (massively parallel rpocessor), спроектированный фирмами Goodyear-Aerospace и NASA Goddard и установленный в мае 1983 г. В этих системах каждый из тысяч процессоров выполняет одну и ту же команду над различными потоками данных. Данные, которые необходимо обработать и объем которых в идеале соответствует размерам матрицы процессоров, вводятся в систему таким образом, что каждый из процессоров имеет в собственной памяти одно подмножество таких данных, например один элемент растра. Затем каждый из процессоров обрабатывает данные, хранящиеся в собственной памяти, а также данные его ближайших соседей (рис. 23.3). Процессор CLIP4 построен из заказных КМОП-кристаллов, спроектированных для работы с тактовой частотой 2,5 МГц. Каждый кристалл содер-жит матрицу размером 2X4 из восьми вычислителей, состоящих из процес-соров, дополнительных логических элементов для параллельной выборки и обработки восьми соседних переменных, необходимых для организации операционного окна, и памяти на 32 бит (плюс несколько одноразрядных регистров) . Реально работающие процессоры DAP построены на обычных ТТЛ ИС, работающих с тактовой частотой 10 МГц (каждый из процессоров содержит ЗУПВ емкостью 4К). Однако уже опробованы кристаллы с четырь-мя процессорами и набором регистров, и предполагается, что в будущем в распределенных матричных процессорах будут использоваться эти кристал- П~~П-П-П-П-П-П-П/7-/7-/7-я-/7-/7-/7-У7 I ! I I I I I I оа а I I ! I I П-П-П-П-П-П- П-п Ввод-** R-R-r-R-R-R ~~R-~fi- Вывод I I I I ! I I II I I I I I I I п-п-л-п-п-л-п-лММММММММ I I I I II I I П-П-П-П-П-П-Л-П6} ! I I I ! I I ! п-п-п-п-п-л-л-п I I I I I I 1 ! л-л-л-л-л-л-л- п МММ! п-л-п-п-л-л-л-п п-п-п-п-п-п-п-л 0 а) Рис. 23.3. Матричные структуры ЭВМ: а - двумерная матрица из 8X8 процессоров. Каждый процессор соединен с четырьмя соседними по горизонтали и вертикали (в других структурах процессоры могут быть соединены в четверки по диагоналям или каждый процессор может быть соединен с шестью соседними). Каждый процессор непосредственно связан с общей памятью (на рис. не показано), а также по изображенным линиям связи с памятью четырех соседних; б - матрица из 1X8 процессоров, каждый из которых соединён с собственной памятью т, а также (через регистры R) с вводом и выводом (иначе это можно рассматривать как вид на приведенную выше структуру 8 Х8 с одной стороны, показывающий, как каждый из процессоров (77) одномерной подматрицы размером 1X8 двумерной структуры размером 8X8 соединяется с собственной памятью М и вводом-выводом через регистры R) лы, а также серийно выпускаемые кристаллы ЗУПВ [17]. В процессоре МРР используются заказные МОП-кристаллы, спроектированные для работы с тактовой частотой 40 МГц. Кристалл содержит восемь процессоров, каждый с 32-разрядным регистром, к каждому из них вне кристалла подключается ЗУПВ емкостью 1К и с циклом 80 не. Базовая команда процессора CLIP4 включает выборку команды (каждые 11 мке) всеми процессорами параллельно и обработку информации из собственной памяти, а также памяти любого из восьми (или всех сразу) непосредственно окружающих данный процессор и ближайших к нему процессоров, т.е. из окружающего окна размером 3X3. Эта команда очень похожа на операции в окне, выполняемые процессорами PICAP и Cytocomputer. Однако ее аппаратная реализация существенно иная, так как процессор CLIP выполняет за одну команду все действия в операционном окне матрицы, в то время как конвейерные системы должны последовательно обрабатывать каждый элемент растра и соседние с ним элементы в процессорах, выполняющих эту команду. Процессоры DAP и МРР не имеют встроенного операционного окна. Их базовая команда состоит из "выборки-сложения", "выборки-дизъюнкции" или какой-либо другой последовательности одной выборки и арифметической или логической операции над одноразрядным срезом данных и данными в аккумуляторе. Это означает, что они должны использовать последовательность до 12 команд, включающую две команды сдвига переменных в диагональных ячейках окна для выполнения одной операции в окне. Длительность выполнения базовой команды в процессоре DAP составляет 250 не, а в МРР ожидается получить длительность выполнения 100 не. Современные большие матричные структуры содержат от 4000 до 16 000 процессоров, но при современной технологии и современных экономических возможностях можно построить гораздо большие системы с 256X256, 512X512, 1024X1024 и более процессорами. Например, построение CLIP4 с 10000 процессоров в 1980 г. обошлось приблизительно в 100 000 дол., т.е. в 10 дол. на процессор. А вот окончательная стоимость: в состав кристалла CLIP4 стоимостью 25 дол. входит 8 процессоров, следовательно, каждый процессор стоит около 3 дол. Стоимость кристалла сотового процессора CLIP и всей системы в целом быстро снижается в результате его перепроектирования; так, сейчас цена кристалла составляет 4 дол., а процессора - 50 центов [4]. Следовательно, система из 250000 или около того процессоров может быть построена в следующие два-три года не более чем за 1 млн дол., а возможно, и значительно дешевле. Это означает, что каждый элемент массива 512X512 телевизионного изображения может запоминаться в памяти отдельных процессоров и все элементы могут обрабатываться за то же время, за которое обычная система может обработать один элемент. Однако матричные системы, построенные к настоящему времени, имеют размеры меньше 512X512 и стоят они намного больше 3 дол. за процессор: процессор размером 64X64 DAP стоит более 1 000 000 дол. в дополнение к 3 000 000 дол. за центральный процессор ICL; процессор МРР, включая стои- 401
a)
2222 2222 2222 2222 4444 4444 4444 4444 S) Рис. 23.4. Матрицы обрабатываемого изображения, большие по размерам, чем матрица процессора: а - подматрицы изображения запоминаются в памяти каждого процессора. Элементы с одинаковыми номерами запоминаются в соответствующих ячейках памяти процессоров. Матрица изображения размером 16X16 элементов располагается и запоминается в структуре 4X4 из 16 процессоров (под номерами с 1 по 16). Память каждого процессора хранит подматрицу изображения размером 2X2 (под номерами a - d); б - подматрицы изображения одинаковых с матрицей процессора размеров обрабатываются по очереди. Иллюстрируется декомпозиция матрицы изображения размером 16X16 на четыре подматрицы размером 4X4, которые вводятся и обрабатываются матричным процессором размером 4X4 по одной в каждый момент времени мость разработки, стоит 5 000000 дол. Как показано на рис. 23.4, массивы данных об изображениях, большие, чем матрицы процессоров, легко могут быть обработаны двумя следующими способами: 1)часть полного массива изображения запоминается в собственной памяти каждого процессора, например (8Х8)-подмассив полного (1024X1024)-массива может запоминаться в каждой ячейке (128 X128) -матрицы процессоров ; 2)часть полного массива изображения, совпадающая по размеру с матрицей процессоров, вводится в матрицу так, что каждый элемент массива изображения запоминается в памяти каждого процессора; \этот процессор повторяется до тех пор, пока не будет обработан весь массив изображения. 402~\ Каждый из этих методов имеет свои недостатки: 1)оба, конечно же, характеризуются гораздо большей продолжительностью обработки, поскольку должен последовательно обрабатываться больший массив меньшей по размерам матрицей процессоров; 2)при первом способе, кроме того, требуется дополнительное время [или (и) оборудование] для индексации подмассива, а также дополнительная память для всего подызображения и всех получаемых результатов преобразований; 3)при втором способе должны обрабатываться окна на внутренних границах, где элементы, прилегающие к обрабатываемому подмассиву, но не входящие в него, должны рассматриваться как часть окна. Это означает, что должно выполняться одно из следующих условий: а)должны постоянно просматриваться в необходимых границах строки и столбцы; б)должны обрабатываться перекрывающие подмассивы, что обусловливает дополнительные затраты времени; в)должно быть добавлено оборудование для запоминания перекрывающихся столбцов изображения, которые могут рассматриваться как его левая или правая граница, и перекрывающихся строк, которые могут рассматриваться как верхняя или нижняя граница. Такие большие матричные системы возможны только благодаря тому, что каждый процессор выполнен настолько простым, насколько это возможно, и все они выполняют одну и ту же команду (что означает, что необходим только один контроллер). В современных матрицах используются процессоры, которые обрабатывают в каждый момент времени один бит данных. Это эффективно для логических операций. Логические операции включают в себя очень важный класс операций обработки изображений, в которых совместно и одновременно проверяются несколько признаков, а получаемая характеристика (часто называемая меткой) считается либо "присутствующей", либо "отсутствующей" в каждой из ячеек. Арифметические и строковые операции, которые должны выполняться над элементами данных длиной, превышающей 1 бит, выполняются достаточно просто, но только по следов ател ьно, побитно, т. е. в так называемом "последовательном по битам" режиме. Это означает, что если должны выполняться, например, 3-, 21-, 33-, 47-, 64- или 89-разрядные арифметические операции или операции сравнения, то их выполнение займет в Зк, 21к9 ЗЗк, 47к, 64к или 89к раз больше времени, чем выполнение соответствующей 1-разрядной операции (здесь к - небольшая постоянная, приблизительно от 2 до 5, определяемая дополнительными затратами). Таким образом, ценой возможного 3-, 64-кратного и более снижения производительности ввиду необходимости последовательной обработки многоразрядных чисел и строк существующие в настоящее время системы дают увеличение скорости обработки в 4 000 - 16 000 раз при параллельной обработке больших массивов чисел. В системах будущего с сотнями тысяч или миллионами процессоров будет достигнуто увеличение скорости обработки на пять, шесть и более порядков. Базовая команда процессора CLIP4 обрабатывает окно размером 3X3 (плюс десятое число, которое берется в качестве второго операнда только из памяти ячейки). Это дает дополнительное десятикратное приращение производительности при условии, что обрабатывается 10 информационных элементов. Вероятно, наиболее важным свойством этого матричного процессора, которое станет наиболее привлекательным в ближайшие 10-20 лет, является то, что он легко может быть расширен. Матрица размером 512X512 - это просто матрица размером 4X4 из матриц, содержащих 128X128 элементов. Наряду с этим следует учитывать количественный фактор, так как по мере увеличения числа изготавливаемых однотипных кристаллов, а также объединяемых однотипных плат и других модулей осуществляется переход к массовому производству. При использовании СБИС-технологий будущего такие параллельные матричные системы будут становиться все более привлекательными из-за простоты и высокой повторяемости их микромодульной структуры. В противоположность этому слишком мало может быть сделано для увеличения мощности современных последовательных ЭВМ. Они быстро приближаются к черте, за которой их невозможно будет сделать более быстродействующими (за исключением объединения специализированных параллельных процессоров в один центральный процессор), так как они скоро достигнут непреодолимого барьера "скорости света". 23.5. МНОЖЕСТВО ВАРИАНТОВ БОЛЕЕ ОБЩИХ СТРУКТУР СЕТЕЙ Из-за ограниченных возможностей матриц, вызванных в основном соображениями стоимости (одноразрядные процессоры, единый контроллер и связи только с соседними процессорами), многие предпочли бы иметь дело с сетями других видов. Было разработано много типов сетей, включая кольцевые [6], «-кубические [25], решетчатые [38], звездные [26], "снежинка" [7], чечевицеобразные [8], древовидные [14], jc-древовидные [2], пирамидальные, и множество структур, описываемых другими графами (см., например, [31, 35]). В нашем случае граф - просто отображение набора подсистем, объединенных в единый мультипроцессор; иногда узлами графа являются отдельные процессоры или память, а не полные ЭВМ. Однако таких систем в действительности было построено очень мало и только две из них с числом процессоров более 50: Cm* [26] и Genoa machine [15]. Число вариантов построения практически бесконечно, поскольку они включают все мыслимые способы соединения все возрастающего по мере совершенствования и удешевления технологии числа процессорных элементов, т.е. все возможные графы. Проблемы, возникающие на этом пути, огромны. Сегодня специалисты еще только приступают к штурму очень сложных проблем проектирования таких многопроцессорных систем, разрабатывая распараллеливаемые алгоритмы, методы программирования и отображения их на сети, а также организуя взаимодействие этого множества различных процессоров, выполняющих одну и ту же программу, для получе- 404Т ния приемлемой эффективности (для ознакомления с этими взаимосвязанными проблемами см. [35 - 37] ). 23.6. АЛГОРИТМИЧЕСКИ СТРУКТУРИРОВАННЫЕ МНОГОПРОЦЕССОРНЫЕ СЕТИ Среди наиболее привлекательных целей выделяется построение сетей, структура которых отражает выполняемый алгоритм. Наиболее интересными примерами таких структур являются древовидные, в особенности большие х-деревья [2] , гипердеревья [9], и матрицы изменяемой конфигурации из обычных ЭВМ [20]. Деревья имеют хорошую структуру для большого числа задач, в которых информация сортируется, сравнивается или каким-либо образом уплотняется и реорганизуется, а также где она запоминается, извлекается или передается. Матрицы имеют хорошую структуру для локальной передачи информации, а введение в них реконфигури-рующих коммутаторов [19] при вычислении быстрого преобразования Фурье [24] и решение многих других задач преобразования информации диктуются непосредственно видом потоков данных. Матрицы одноразрядных процессоров, рассмотренные ранее, также являются хорошим примером таких алгоритмически структурированных систем. Пирамидальные многопроцессорные системы, рассматриваемые далее, считаются наилучшими, поскольку они очень эффективны не только при параллельной локальной обработке, но и при глобальных передачах и преобразованиях информации. 23.7. АРХИТЕКТУРА АППАРАТНЫХ СРЕДСТВ ПИРАМИДАЛЬНЫХ МАТРИЧНЫХ МНОГОПРОЦЕССОРНЫХ СИСТЕМ Возможно несколько вариантов построения матриц, зависящих от вида связей между процессорами. Однако начнем с конкретного примера. В одной из простейших и наиболее привлекательных схем каждый процессор связан с четырьмя соседними ("четырехсвязный процессор") таким образом, что может получать одно слово информации из любого из четырех запоминающих устройств (или из пятого, собственного). Один из простейших путей начать построение пирамиды - взять матрицу и, начиная с любого из углов (пусть из левого верхнего), связать каждую подматрицу из 2X2 процессоров с новым процессором, в то же время связывая полученную группу новых процессоров в 4-связную матрицу. Это дает еще одну матрицу, число процессоров в которой составляет 1/4 от их числа. Теперь продолжим связывание подматриц размера 2X2 в один узел верхней (по иерархии) матрицы, пока не достигнем "наивысшей" матрицы с одним-единственным узлом. Это дает пирамиду с числом матриц, равным log (АО+1, где матрица у основания имеет размер NXN, а размер каждой из верхних матриц составляет одну четвертую размера ближайшей снизу матрицы. Диаметр, т. е. кратчайшее расстояние между наиболее удаленными узлами такой пирамиды, равен log4 (АО • 0 ... 63 64 65 66 67 68 69 ... 78
|
