Раздел: Документация
0 ... 64 65 66 67 68 69 70 ... 78 П f! Г. Г П /7 Л Л пппппппп пппппппп пппппппп ппппппппп п п пСлойОп ппппппппп п п пСлой 1пп ппппппппп п п п п пСлой 2 л п п п ппппппппп п л л л л лСлойЗ п п п л л л п л СлойОСлой! Слой2 СлойЗ (основание){вершина) а)5) / \\ / пп ПпПпр Вид сбоку„/ \п Вид сверху в) (одна строка) Рис. 23.5. Построение иерархической пирамиды матриц убывающего размера; четырех-слойная пирамида с основанием размером 8X8 и конвергенцией 2X2 с каждого слоя на следующий: а - первоначально сгруппированы четыре матрицы процессоров, образующие слои пирамиды; б - эти матрицы (слои) последовательно составлены в структуру по порядку убывания размера (вид сбоку, показывающий лишь одну строку каждого слоя) ; в - процессоры связаны от слоя к слою так, что каждый "предок" (77 ) имеет достаточное число "потомков" (77п) , а "потомки" имеют предков 23.8.ПОСЛЕДОВАТЕЛЬНОЕ ОБЪЕДИНЕНИЕ МАТРИЦ ДЛЯ ПОСТРОЕНИЯ ПИРАМИДЫ Пирамида может быть построена последовательным составлением меньших по размеру матриц, как показано на рис. 23.5. Из рисунка видно, каким образом матрица может быть связана с матрицей меньшего уровня, которая вдвое больше порождающей матрицы по длине и ширине и поэтому содержит вчетверо больше процессоров. 23.9.СОСТАВЛЕНИЕ ПИРАМИД СОЕДИНЕНИЕМ В МАТРИЦУ КАЖДОГО ИЗ ЯРУСОВ ДЕРЕВА Еще одна из иллюстративных процедур построения начинается с дерева четвертого порядка (т.е. с корневого узла дерева, связанного с четырьмя узлами-потомками, каждый из которых, в свою очередь, соединяется далее с четырьмя узлами-потомками и так до достижения концевых узлов-почек) . Таким образом, каждый новый ярус (т.е. слой потомков) содержит в четыре раза больше узлов, чем предыдущий. Теперь добавим горизонтальные линии связи между узлами-братьями (узлами того же слоя) для преобразования каждой из групп одного слоя в матрицу. Корневая матрица - это матрица размером 1X1, содержащая единственный узел. Матрица в следующем слое дерева - матрица размера 2X2 из четырех потомков корневого узла, дополненная линиями связи между ними, т.е. братскими связями. Каждый набор из четырех потомков узла также геометрически представляется в виде подматрицы размера 2X2, помещенной рядом с подматрицами-братьями и другими соседними узлами своего слоя. Таким образом, двумерные геометрические связи матрицы покрываются топологией дерева. Термин квадродерево был использован для определения варианта данной структуры - дерева, наибольший из слоев которого преобразован в матричную структуру или используется для ввода образа матрицы. Промежуточные ярусы не имеют горизонтальных линий связи для образования матричной структуры. Квадродеревья - очень полезные структуры для решения задач сжатия, запоминания, описания и восстановления больших двумерных изображений. Октодерево имеет восемь потомков, организованных в трехмерную пространственную конструкцию размером 2X2X2, вследствие чего оно может использоваться как четырехмерное дерево, воспринимающее и обрабатывающее трехмерные изображения (или другие информационные множества), вводимые в его базовую матрицу - матрицу почек. В более общем виде можно определить С-конвергентное1 /)-мерное дерево CD. Например: дерево размера 22 - квадродерево, дерево размера 23 - окто дерево, дерево размера З2 - дерево степени 9, в котором каждый узел имеет девять потомков, организованных в подматрицу размера 3X3. Дерево размера З5 - есть дерево степени 243, где каждый узел имеет 243 потомка, организованных в пятимерную конструкцию, каждая из сторон которой образована тремя узлами. Мы можем расширить это определение включением числа слоев Р в дереве в деревья (Р, Р. Число слоев равно \ogDB, где В - число "почек" дерева. Естественно, что B=NXN, где N - длина и ширина базовой матрицы размера 7VX7V, которая присоединяет "почки". Таким образом, дерево 22, log22 (256) является четырехсловным квадро-деревом, базовая матрица которого имеет 256 "почек", организованных в матрицу размера 256X256. Пирамида CD, Р, S похожа на дерево CD, Р, но с добавлением в каждом слое линий связи с братьями для образования матрицы. 23.10. РАЗЛИЧНЫЕ СПОСОБЫ ВИДОИЗМЕНЕНИЯ ПИРАМИД Возможен ряд вариаций на основе пирамидальных построений. Наиболее интересными являются следующие. 1. Конвергенция (С) может быть любым небольшим целым числом. (Возможен также выбор дробных значений посредством интерполяции, что может явиться привлекательным способом расширения последовательности преобразований в пирамиде.) 1 Ввиду отсутствия соответствующего термина в русском языке, переводим слово "convergence" как конвергенция. Конвергенцию можно понимать как показатель связи при объединении подматриц в узлы. - Прим. перев. 2.Возможны разные значения конвергенции между различными парами слоев. 3.Может отсутствовать конвергенция между частью пар или всеми парами слоев (в этом случае система преобразуется в трехмерную прямоугольную матрицу), т.е. показатель связи С может быть установлен равным 1. 4.Конвергенции по строкам и столбцам могут различаться (это может быть полезным при обработке прямоугольных, а не квадратных изображений) . 5.Родители могут располагаться на расстоянии S (одного шага) друг от друга. Тогда при С = S пирамида не имеет перекрытия; при OS каждый из предков делит потомков с непосредственными соседями, образуя перекрытие. Привлекательные возможности имеются при С-Ъ и S =2, когда каждый из родителей связан с окном из 3X3 потомков и родители расположены над каждым вторым потомком (что дает связь 2X2) . 6.В отличие от организации связей в соответствии с рангом дерева или пирамиды, дающей пирамиды размером О (log JV), в другой очень простой схеме они организуются за TV шагов. Это достигается простым построением матриц со связями между диагоналями наряду со связями между ортогональными соседями, а также ликвидацией всех узлов вне пирамиды, как показано для двумерного случая на рис. 23.6. В отличие от ранее определенных и описанных пирамид размером О (log TV) такие пирамиды можно рассматривать как пирамиды О (Л) . Такие матрицы могут оказаться пригодными для решения многих практических задач, но по сведениям, которыми располагает автор, они совершенно не исследованы. При построении этих матриц, имеющих достаточно большие размеры для обработки реальных изображений, т.е. с базовой матрицей размера 512X512 и более, присущие им расстояния N/2 для преобразования изображения и передачи сообщений, а также число узлов, равное О (N3 ), а не О (N2 ), представляются чрезмерно большими. 7.Связи с братьями и потомками могут меняться, например девять линий связи с братьями и четыре с потомками или наоборот. 8.Пирамида может быть усечена, когда небольшая верхняя часть матрицы удаляется или заменяется более мощными вычислителями другого типа. П п-п-п п-п-п-п-п л-п-п-п-п-п-п Рис. 23.6. Двумерная пирамида размером O(N). Каждый процессор соединен по диагоналям с двумя соседними (на рис. не показано) в двух прилегающих слоях (или только с одним из соседей в меньшем верхнем слое, если процессор находится на периферии) . Таким образом, каждый слой содержит на два процессора меньше, чем соседний нижний слой, а вся пирамида состоит из N/2 слоев (N - длина одной стороны пирамиды)/ 23.11.РЕАЛИЗАЦИЯ ПИРАМИД Большое и все возрастающее число специалистов занимается анализом свойств пирамид и их применением, и множество алгоритмов уже приспособлено к выполнению базовых операций по обработке изображений [10, 13, 18, 29, 32, 33]. Однако лишь три-четыре специалиста основательно исследовали вопросы архитектуры пирамид и подошли к предложению многопроцессорных систем пирамидальной архитектуры [5, 27, 28, 30, 34-37]. Только одна из них в настоящее время реализована конструктивно. Этот пирамидальный процессор обработки изображений PIP (Pyramid image processon) разработан совместно фирмой Boeing Aerospase и Вашингтонским университетом [21] на основе идей [27, 28, 30]. Планируется, что такой процессор будет иметь базовую матрицу, состоящую из 128Х128 процессоров. Он представляет собой полную пирамиду с конвейеризацией глубиной 2 без перекрытий. Таким образом, вся пирамида содержит восемь слоев: 128X128, 64X64, 32X32, 16X16, 8X8, 4X4, 2X2 и 1X1 на вершине. Каждый процессор в составе PIP связан с четырьмя потомками в нижнем слое (это и дает связи вида 2X2), восемью соседними (а также с собственной памятью) в своем слое, а также с его единственным родителем. Таким образом, каждая базовая команда может выбирать слово информации из любого набора блоков памяти этих четырнадцати процессоров (включая собственную) и производить вычисления на основе этой информации. Это означает, что информация может передаваться вверх и (или) вниз или по горизонталям матрицы процессоров. В настоящее время разрабатывается кристалл, который объединит 64 процессора (связанных с ЗУПВ кристалла) одним из двух способов в зависимости от того, насколько хорошо отдельные модули, которые уже проходят проверку, можно будет объединять: либо 4 процессора по отдельности будут производить обработку 16 элементов растра каждый (в целом за 2 мкс), либо 8 процессоров будут поеледовательно обрабатывать по 8 элементов каждый (всего за 1 мкс). 23.12.АРХИТЕКТУРА ПРОБЛЕМНО-ОРИЕНТИРОВАННЫХ СИСТЕМ ДЛЯ ПРЕОБРАЗОВАНИЯ ПОТОКОВ ДАННЫХ Программа разрабатывается для реализации алгоритма, который, в свою очередь, выбирается для выполнения набора преобразований информации (данных). Как преобразования, так и информация имеют собственную структуру, и хороший алгоритм должен следовать этой структуре. Такой проблемно-ориентированный алгоритм наилучшим образом размещается в многопроцессорной сети так, что операции организуются как на сборочном конвейере, а информация продвигается также как бы через конвейер. Это дает поток, похожий на транспортный, но уже поток данных о двумерном изображении, и этот поток проходит по трехмерной структуре, т. е. этот процесс гораздо сложнее, чем в современных одномерных конвейерах. Такая структура имеет некоторые аналогии с живым мозгом, через который проходят данные от органов чувств. Такая хорошо организованная сеть может в действительности содержать подсистемы различной структуры, в том числе и матрицы. Она также может содержать программно-управляемые коммутаторы, которые могут использоваться для реконфигурации структуры с целью лучшего соответствия различным программам и даже различным процессам одной программы. Большие двумерные образы прекрасно размещаются в больших матричных структурах, и большие матричные многопроцессорные системы способны очень эффективно производить последовательности операций по обработке поэтапно преобразуемого изображения. Пирамидальные процессоры в дополнение к этому позволяют программисту свертывать и сжимать запоминаемую информацию о преобразованном изображении, когда необходимо сократить объем этих данных. Например, при использовании окна размером 3X3 для вычисления градиента изображение может быть передано на следующий слой 3-конвергентной пирамиды. Когда несколько штрихов или других элементов, содержащихся в окне размером 2X2, 3X4 или NXN, объединены в один элемент высокого уровня, матрица, в которой запоминаются их данные, может быть соответственно меньшего размера. В пирамиде есть локально-соседние связи, соответствующие обработке информации, взаимодействия в которой локальны, как и связи, подходящей для эффективного сокращения информационных потоков и передачи сообщений структуры. Представляется, что пирамидальные процессоры потенциально должны обеспечивать чрезвычайно высокую мощность при обработке потоков изображений в реальном масштабе времени (например, с телевизионной камеры, выдающей кадр изображения каждые 30 мс) благодаря конвейерной организации обработки таких двумерных изображений при сложной последовательности операций поэтапно нарастающей глобальности, выполняемых в различных слоях трехмерной пирамиды. 23.13. СООТВЕТСТВИЕ МАТРИЧНЫХ И ПИРАМИДАЛЬНЫХ ПРОЦЕССОРОВ ТЕХНОЛОГИИ СБИС Процессоры, используемые в матричных и пирамидальных системах, обычно стремятся сохранить чрезвычайно простыми. Почти во всех вариантах систем использовались одноразрядные процессоры с числом вентилей от 100 до 800. Причиной этого является то, что для достижения четырехкратного и большего увеличения скорости и вычислительной мощности обработки благодаря последовательному наращиванию числа параллельно работающих процессоров архитекторы систем выбирали для использования наиболее простые из возможных одноразрядные процессоры, обеспечивая выполнение К одноразрядных операций для обработки /-разрядных чисел или строк. По-видимому, объем памяти, необходимый каждому процессору, является функцией от общего объема памяти, необходимого для обработки изображений или других наборов данных, поступающих в систему. Поэтому каждый процессор нуждается в памяти относительно небольшого объема (реализованные системы снабжены памятью от 32 до 4096 бит на процессор). 410/ Процессоры объединяются в высокорегулярную микромодульную систему, которая является одной из наиболее пригодных для реализации в виде СБИС при высокой плотности упаковки. В настоящее время по четыре, восемь и более таких одноразрядных процессоров выпускаются в одном кристалле СБИС. Ввиду высокоинтег-рированной микромодульной конструкции таких систем вскоре должно стать возможным производство в одном кристалле сотен и даже тысяч процессоров с собственной памятью для каждого. Это резко контрастирует с реализацией в СБИС обычных однопроцессорных систем, для которых (даже при возможности упаковки одного или нескольких процессоров на одном кристалле) останется необходимым наличие нескольких кристаллов для работы с несколькими миллионами байт быстродействующей памяти каждого из процессоров. Многопроцессорные матричные и пирамидальные системы из 1024 или более процессоров можно будет построить на основе матрицы размером 16X16, т.е. всего из 256 кристаллов, в каждом из которых содержится матрица размером 64X64 из 4096 400-элементных процессоров с памятью объемом 512 бит. Такая матрица или пирамида, основанием которой была бы матрица, содержащая не более одной трети числа процессоров в основании, может быть реализована на достаточно небольшом числе кристаллов со степенью интеграции 107, упакованных на одной пластине. Высокорегулярная микромодульная матричная или пирамидальная структура является особенно привлекательной для изготовления отказоустойчивой СБИС с интеграцией на уровне пластины. 23.14. ЗАКЛЮЧЕНИЕ В начале данной главы исследуются и описываются параллельные матричные, конвейерные и некоторые другие многопроцессорные системы, как обеспечивающие огромный потенциальный рост производительности и вычислительной мощности. Действительно, любой граф, узлами которого являются отдельные процессоры, а дугами - непосредственные связи между ними, сейчас можно разместить в конкретной многопроцессорной системе. Затем внимание концентрируется на сравнительно новой топологии, которая представляется особенно подходящей для обработки изображений, распознавания образов и машинного зрения. Это топология, при которой f ю сл е до в ате л ьн о уменьшающиеся матрицы объединяются в единую пирамидальную структуру. Каждый слой пирамидальной системы может достигать такой же потенциально высокой производительности обработки, как и сопоставимые по размерам матричные процессоры, поскольку каждый ее слой в сущности и является матричным процессором. К тому же все слои пирамидальной системы могут работать одновременно. Важно и то, что внутренняя древовидная топология пирамиды определяет возможность накопления и объединения информации но мере поэтапного преобразования изображения. Части одного и того же объекта, которые первоначально далеко отстояли друг от друга, поэтапно сближаются (и в то 0 ... 64 65 66 67 68 69 70 ... 78
|
