Раздел: Документация
0 ... 26 27 28 29 30 31 32 ... 78  -о-о Рис. 9.3. Прямое отображение графа связи процессора БПФ. Показаны вованные пути передачи данных только задейст- ды, но для других алгоритмов, например ветвящихся, это существенно.) Для завершения второго этапа мы просто программируем процесс в приведенной здесь форме и указываем, что все ПЭ работают по одной программе. При подготовке программы к выполнению контроллер ВППК-процессора загружает матрицу программами (используя "скелет", который на рисунке не показан). Коммутаторами задается (в общем поле памяти) структура связей, соответствующая БПФ. Каждому ПЭ задается своя объектная программа внутренних вычислений. Затем контроллер выдает коммутаторам команду, по которой устанавливается конфигурация, в результате чего процессоры оказываются соединенными, как показано на рис. 9.3. По этой же команде ПЭ начинают выполнять заложенные в них программы и начинается конвейерное выполнение алгоритма БПФ, Соединение ПЭ остается неизменным до выдачи контроллером специальной команды перестройки, например, для реализации другого алгоритма. 9.3. УНИВЕРСАЛЬНЫЙ СИГНАЛЬНЫЙ ПРОЦЕССОР НА ОСНОВЕ ВППК-ПРОЦЕССОРА Широкое распространение алгоритма БПФ позволяет рассматривать ВППК-процессор как универсальный сигнальный процессор. Отметим, что, хотя рассматриваемый алгоритм был конвейеризован, ВППК-процессор не является систолической матрицей. Межпроцессорные соединения не огра- 178 *.-е-н
1.1 -е- о о хг-©~  о  г.1 О ) о о о □ о (j) О ОJd- 3.2 2.3 -е- 1.2 1.3  -е- г.г О  -е-ч о о oysi о о е г л о о ф о □ о о о  3.3  о 1А е- о о о oV ЗА Ф о о о □ о (3 о о "Ху Рис. 9.4. Усовершенствованное отображение графа, приведенного на рис. 9.2 ничены связью с ближайшими соседями. С помощью коммутаторов можно обеспечить связи различной структуры, реализующие как фиксированные систолические матрицы, так и структуры более общего вида. Это позволяет при проектировании систем обработки сигналов рассматривать более широкий класс алгоритмов, чем при использовании программируемых систоли- ческ их матриц [5, 6]. Возможность программирования межпроцессорных связей различной структуры позволяет оптимизировать вычислительное устройство. В зависимости от целевой функции наилучшим может быть признано то или иное решение. Поскольку коммутаторы вносят некоторую задержку распространения сигнала, оптимизация может сводиться к уменьшению длины пути передачи данных. Тщательный анализ показывает, что для рассматриваемой простой задачи БПФ существует возможность уменьшить длину линий связи с помощью организации однонаправленного потока данных. Структура межпроцессорных линий связи типа "ближайший сосед", уменьшающая длину соединений и сокращающая требуемую ширину коридора до единицы, показана на рис. 9.4. Отметим, что такая структура является просто еще одним отображением графа на рис. 9.2, изменены лишь направления, но которым данные принимаются и отсылаются, а программы ПЭ остаются неизменны- 179  Рис. 9.5. Тасующий граф с 64 вершинами ми. (Компилятор назначает порты соответствующих направлений, освобождая от этих забот разработчика.) Проблема получения графа со связями типа "ближайпшй сосед или хотя бы с локальными связями для алгоритма БПФ большой размерности представляет значительный интерес. Результаты, полученные в [7], показывают, что асимптотически подобные графы с перестановкой вершин не могут быть отображены на матрицу с загрузкой всех процессорных элементов, если ширина коридора будет меньше 0(Vn/log п), где п - число процессоров в матрице. При этом возможность получения локальных связей кажется маловероятной даже для матриц, удовлетворяющих этому требованию. Однако такие асимптотические результаты могут вводить в заблуждение. В работе [8] неожиданно показан эффективный способ отображения графов тасовки, а в [9] подобный граф с 64 вершинами отображен на матрицу с единичной шириной коридора. Последний результат представлен на рис. 9.5. Суть его в том, что, разделив задачу параллельного программирования на две части, можно решать каждую из них в значительной степени независимо друг от друга. Быстрое преобразование Фурье является наиболее изученной операцией обработки сигналов, и существует большое число алгоритмов, реализующих это преобразование. Поскольку нет ограничений, вынуждающих в ВППК-. процессоре использовать только систолические алгоритмы, можно исследовать достоинства других вычислительных методов. В работе [10] проанализированы Восемь алгоритмов БПФ исходя из их реализации на СБС и показано, что некоторые из них пригодны дтя реализации с помощью ВППК-про-цессоров. 9.4. НЕКОТОРЫЕ ПРОБЛЕМЫ РЕАЛИЗАЦИИ Мы уже сформулировали условия, определяющие целесообразность использования ВППК-процессоров для решения всевозможных задач обработки сигналов. Хотя обработка сигналов как сфера применения "подходит" для ВППК-процессоров вследствие высокой регулярности и параллелизма алгоритмов, другие характеристики алгоритмов решения задач в этой области делают ее не столь привлекательной дтя универсального решения как с помощью ВППК-процессоров, так и программируемых систолических матриц. В связи с этим следует отметить потребность в очень вы- сокой производительности и тот факт, что сигнальные процессоры являются составной частью систем, решающих только одну задачу. Кратко рассмотрим методы специализации ВППК-процессоров, направленные на увеличение производительности. Очевидным способом увеличения производительности являйся построение специализированных ВППК-машин. Можно заменить ОЗУ на ПЗУ как в ПЭ, так и в коммутаторах. С коммутаторами можно поступить еще лучше: можно их изъять, если в сигнальном процессоре используется только одна структура связи. Даже если в сигнальном ВППК-процессоре реализуется несколько алгоритмов или алгоритм требует нескольких соединений различных видов, то все равно можно отказаться от значительного числа коммутаторов. В любом случае получится хотя и небольшой, но все-таки выигрыш в площади (площадь коммутаторов невелика), уменьшится задержка распространения сигнала (которая может стать незначительной, за исключением задержек в очень длинных линиях передачи данных), упростится или вообше может быть устранен контроллер и полностью потеряется гибкость - "зашитый" алгоритм не может быть изменен или улучшен. В каждом конкретном случае следует оценить особо, представляют ли эти достоинства интерес. Если алгоритм соответствует ОКМД-управлению, программная память может быть устранена при соответствующей переработке контроллера. Быстродействие может быть увеличено путем замены процессора с памятью схемной реализацией простейших операций. В работе [1] было показано, как ВППК-архитектура может быть использована в качестве основы методологии проектирования схемных решений. По существу, этот процесс представляет собой последовательное уточнение, при котором вычисления в ПЭ рассматриваются как задачи, которые необходимо решить на ВППК-машине с более примитивными ПЭ. В пределе сложность ПЭ может быть уменьшена н они могут быть сьедены к простым вентильным элементам, реализуемым непосредственно в СБИС. При современной технологии только небольшая часть ВППК-матрицы помещается на одном кристалле кремния. Хотя мы рассчитываем на улучшение, более серьезный прогресс может быть достигнут при использовании интеграции на целой полупроводниковой пластине. В [11] описаны метод проектирования полупроводниковой пластины и использование коммутаторов дтя обхода поврежденных элементов. В результате получается единая компактная регулярная структура, содержащая сотни ПЭ, требуемых для обработки сигналов. 9.5. ЗАКЛЮЧЕНИЕ Рассмотренный процессор может использоваться как универсальное устройство обработки сигналов, обеспечивающее возможность наиболее удобной реализации алгоритма и допускающее экспериментирование. Более того, его разработка является первым шагом на пути к дальнейшей специализации, позволяющей уменьшить сложность, увеличить быстродействие и снизить стоимость. [1] L. Snyder, "Configurable, Highly Parallel (CHiP) Approach to Signal Processing Applications," Proc. Tech. Symp. East 82, SPIE, 1982. [2] L. Snyder, "Introduction to the Configurable, Highly Parallel Computer," Computer 75(l):47-56(Jan. 1982). [3] L. Snyder, "Overview of the CHiP Computer," in J. P. Gray, ed., VLSI 81, Academic Press, New York, 1981, pp. 237-246. [4] H. S. Stone, "Parallel Processing with the Perfect Shuffle," IEEE Trans. Comput., C-20(2):153-161 (1971). [5] K. Bromley, J. J. Symanski, J. M. Speiser, and H. J. Whitehouse, "Systolic Array Processor Development," in H. T. Kung, B. Sproull, and G. Steele, eds, VLSI Systems and Computations, Computer Science Press, Rockville, Md, 1981, pp. 273-284. [6] Y. Dohi, A. L. Fisher. H. T. Kung, and L. Monier, "The Programmable Systolic Chip: Project Overview," in L. Snyder, L. J. Siegel, H. J. Siegel, and D. B. Gannon, eds, Algorithmically Specialized Computer Organizations, Academic Press, New York, 1983. [7] C. D. Thompson, "A Complexity Theory for VLSI," Ph.D. thesis, Carnegie-Mellon University, 1980. [8] F. T. Leighton and G. L. Miller, "Optimal Layouts for Small Shuffle-Exchange Graphs," in J. P. Gray, ed, VLSI 81, Academic Press, New York, pp. 289-300, 1981. [9] P. Morrissett, "Observations on Graph Embeddings," Blue CHiP Project Notes, Nov. 1981. [10] C. D. Thompson, "Fourier Transform in VLSI," Tech. Rep. UCB/CSD 83/105, University of California at Berkeley, 1982. [11] K. S. Hedlund and L. Snyder, "Wafer Scale Integration of Configurable, Highly Parallel Processors," Proc. Int. Conf. Parallel Process., IEEE, pp. 262-264, 1982. 10 УВЕЛИЧЕНИЕ ДОЛИ ВЫХОДА ГОДНЫХ СБИС ЗА СЧЕТ ОБЕСПЕЧЕНИЯ СВОЙСТВА ОТКАЗОУСТОЙЧИВОСТИ СИСТОЛИЧЕСКИХ СТРУКТУР Р. Кун1 10.1. ВВЕДЕНИЕ О проектировании отказоустойчивых систолических структур известно очень мало. Особенно это относится к области методов повышения выхода годных БИС (в процессе их изготовления). Степень интеграции можно повысить двумя способами: уменьшением минимальных геометрических размеров (элементов на кристалле) и увеличением размеров самого кристалла. Если существующая технология не позволяет изготовить устройства слишком большого размера, то в случае, когда допустимо увеличение числа дефектов, можно немедленно воспользоваться вторым способом. Технологические приемы интеграции на уровне целых полупроводниковых пластин как раз основаны на втором способе [ 1, 3, 4, 6]. В большинстве подходов при интеграции на уровне целых полупроводниковых пластин предусматривается соединение работоспособных узлов после изготовления. В результате получается нерегулярная змеевидная одномерная структура связанных между собой процессорных элементов, в которую не попадают дефектные элементы (рис. 10.1,а). Однако этот прием непригоден для двумерных структур. Метод структурной отказоустойчивости1 позволяет изготавливать одномерные и двумерные структуры при наличии дефектных элементов. В общем случае отказоустойчивость можно обеспечить при наличии избыточности. Избыточность может быть двух видов: за счет увеличения объема аппаратуры или времени вычислений. Некоторые методы изготовления СБИС на целой пластине требуют увеличения объема аппаратуры, но ухудшают эффективность быстрых локальных связей [2]. Упомянутые методы сохраняют локальность связей, но неявно используют аппаратную избыточность в виде дополнительных функциональных элементов. В противоположность этому методы структурной отказоустойчивости основаны на временной избыточности. Поскольку реализация многопроцессорных систем на кристалле стала возможной только благодаря технологии изготовления СБИС на целой пластине, попытаемся рассмотреть применение этой технологии для создания, во-первых, высокопараллельных и, во-вторых, отказо-  Рис. 10.1. Сравнение методов интеграции на уровне целой полупроводниковой пластины (а) и структурной отказоустойчивости (б) для случайного распределения точечных дефектов: О - используемый функциональный ПЭ; X - неиспользуемый дефектный ПЭ; + - неиспользуемый функциональный ПЭ « В оригинале interstitial fault-tolerance. Так как буквальный перевод не объясняет смысла термина, мы переводим его как "структурная отказоустойчивость". - Прим. ред. 0 ... 26 27 28 29 30 31 32 ... 78
|
