Раздел: Документация
0 ... 17 18 19 20 21 22 23 ... 78 [3] E. R. Davidson, "The Iterative Calculation of a Few of the Lowest Eigenvalues and Corresponding Eigenvectors of Large Real Symmetric Matrices," J. Сотр. Phys., /7:87-94 (1975). [4] J. J. Dongarra et al., UNPACK Users Guide, SIAM, Philadelphia, 1979. [53 EISPACK The associated guide is published as Lecture Notes in Computer Science, Vol. 51, by B. S. Garbow et al, Springer-Verlag, New York, 1977. [6] T. Ericsson and A. Rube. "The Spectral Transformation Lanczos Method in the Numerical Solution of Large, Sparse, Generalized, Symmetric Eigenvalue Problems," Math. Сотр., 54:1251-1268 (1980). [7 A. M. Finn, F. T. Luk, and C. Pottle, Systolic Array Computation of the Singular Value Decomposition (preprint), 1981. [8] D. Heller, "A Survey of Parallel Algorithms in Numerical Linear Algebra," SIAM Rev 20:740-777 (1978). [9] International Mathematical Statistical Library (IMSL), Sixth Floor-GNB Building, 7500 Beilaire, Houston, TX 77036. [10] P. Maissl, A Priori Prediction of Roundoff Error Accumulation in the Solution of a Super-Large Geodetic Normal Equation System, NOAA Prof. Paper 12, NOAA, Rock-ville, Md., 1980. [11] Numerical Algorithms Group (NAG), 7 Banbury Road, Oxford OX2 6NN, England. [12] B. N. Parlett, The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, N.J., 1980. (Called SEP in this paper.) [13] B. N. Parlett, and D. Taylor, A Lookahead Lanczos Algorithm for Unsymmetric Matrices, Math Сотр., 44 (to appear). [14] A. Ruhe, "The Two-sided Arnoldi Algorithm for Nonsymmetric Eigenvalue Problems," in B. Kagstrom and A. Ruhe, eds., Matrix Pencils, Springer-Verlag, New York, 1982. [15] Y. Saad, Chebyshev Acceleration Techniques for Solving Nonsymmetric Eigenvalue Problems, Math. Сотр., 41 (to appear). [16] В. T. Smith, et al. Matrix Eigensystem Routines-EISPACK Guide, Lecture Notes in Computer Science No. 6, Springer-Verlag, New York, 1974. [17] G. W. Stewart, A Bibliographic Tour of the Large Sparse Generalized Eigenvalue Problem, in J. R. Bunch and D. J. Rose, eds., Sparse Matrix Computations, Academic Press, 1976, pp. 113-130. [18] M. Heath, ed. Sparse Matrix Software Catalog (1982), available from Mathematics and Statistics Research Dept., Oak Ridge National Laboratory, Oak Ridge, TN. J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, New York, 1965. [20] L H. Wilkinson, and C. Reinsch, 1971. Handbook for Automatic Computation, Vol. II: Linear Algebra, Springer-Verlag, New York, 1971. [21] R. P. Brent, and S. P. Luk, "Computing the Cholesky Factorization Using a Systolic Architecture," Proceedings of the 6th Australian Computer Science Conference, Sydney, Feb. 1983. [22] L. Snyder, "The Role of the CHiP Computer in Signal Processing," Proceedings of USC workshop on VLSI and Modern Signal Processing, Nov. 1982, p. 133. [23] S. Y. Kung and Gal-Ezer, in this volume. [24] R. Schreiber, "A Systolic Architecture for Singular Value Decomposition," Proc. of 1st International Coltoq. on Vector and Parallel Computing in Scientific Applications, INRIA, Paris (1983). ЧАСТЬ II ПАРАЛЛЕЛЬНЫЕ МАТРИЧНЫЕ ПРОЦЕССОРЫ-АРХИТЕКТУРА И ЯЗЫКИ ВВЕДЕНИЕ Темой части II являются архитектуры параллельной обработки, реализованные в виде СБИС. Практическое значение большинства теоретических исследований в области обработки сигналов, включая работы, обсуждающиеся в ч. I, определяется в конечном счете их вычислительной осуществимостью. При обработке данных в реальном масштабе времени это особенно сильно зависит от возможностей параллельной обработки: от скорости и объема обрабатываемой информации, предоставляемых существующими вычислительными машинами. Появление устройств с высокой плотностью компоновки, высокоскоростных СБИС, а также средств автоматизированного проектирования ускорило революцию в архитектурном проектировании. Хотя при высокой степени интеграции возможно обеспечить максимальный параллелизм, и тем самым почти неограниченное аппаратное обеспечение при очень низкой стоимости, имеются отдельные ограничения, обусловленные технологией реализации связей, сложностью разработки, тестирования и т.д. Следовательно, имеется настоятельная потребность в новой методологии проектирования систем на СБИС. С целью увеличения потенциальных возможностей СБИС в области обработки сигналов системное проектирование должно охватывать широкий спектр дисциплин и координировать разработку языка программирования, архитектуры вычислителя и его практического применения. До недавнего времени решение больших вычислительных задач обеспечивалось высокопроизводительными суперкомпьютерами, включая конвейерные компьютеры, матричные процессоры и многопроцессорные системы. Разработка этих вычислительных систем требует тщательного исследования способов организации параллельных вычислений, эффективного программирования и оптимизации ресурсов. Однако универсальное назначение этих машин ведет к усложнению системной организации и резко повышает "накладные расходы" в системных операциях. Эти ЭВМ не пригодны для обработки в реальном масштабе времени, где должна быть обеспечена высокая производительность. Удовлетворить требования высокоскоростной обработки сигналов могут специализированные вычислители. Имеются два типа специализированных вычислителей. Первый характеризуется негибкой и жестко специализирован-126 ной структурой. Второй допускает программируемость и реконфигурируемость. "Жесткие" процессоры применимы при обработке сигналов в реальном масштабе времени, так как они обеспечивают высокую скорость обработки. Однако специализация аппаратных средств часто приводит к длительным циклам проектирования и высокой стоимости. С появлением современного алгоритмического (архитектурного) анализа программируемые (ре-конфигурируемые) параллельные процессоры сигналов стали не только практически реализуемыми, но и во многих случаях более экономичными, чем "жесткие" машины. Поэтому в ч. II существенное внимание уделяется этим параллельным процессорам, точнее, исследуются различные аспекты анализа параллельных алгоритмов, разработки параллельных архитектур и языков программирования параллельных алгоритмов. Эти фундаментальные исследования, по нашему мнению, должны обеспечить теоретическую основу будущих вычислительных систем обработки сигналов на СБИС. С учетом революционных изменений в технологии СБИС должны использоваться новые проработанные концепции и методы архитектурного (алгоритмического) проектирования современных систем обработки сигналов. Основным требованием методологии проектирования сверху вниз является фундаментальное понимание разработчиком методов анализа алгоритмов. Хотя для последовательных алгоритмов эта область исследований хорошо проработана, для случая параллельной обработки требуются большие нововведения. Новые идеи необходимы в выявлении параллелизма, связей, зависимости данных, оценки свойств и общности между алгоритмами. Например, пока реализация внутренних соединений в СБИС остается проблемой, локальность рекурсивных алгоритмов будет иметь решающее значение и роста эффективности можно ожидать тогда, когда алгоритм подготовлен с учетом сбалансированного распределения работ и с соблюдением требования локальности (т.е. коротких линий связи). Распределение нагрузки и потока информации является основным направлением в разработке СБИС-алгоритмов и, в конечном счете, приводит к новым проектам архитектуры и языка. Впервые эти понятия для СБИС-алгоритмов появились при разработке систолических матриц в публикации Н. Т. Kung, С. Е. Leiser-son. "Systolic Array (for VLSI)" [Sparse Matrix Proc, SIAM, 1978]: "Систолическая система представляет собой сеть процессоров, которые ритмически обрабатывают и пересылают данные через систему. Физиологи используют слово "систола" для обозначения ритмических регулярных сокращений сердца, которое прокачивает кровь по артериям сквозь тело. В систолической вычислительной системе функции процессора аналогичны функциям сердца. Каждьш процессор регулярно "проталкивает" данные с входа на выход, в каждый момент времени выполняет некоторый вид вычислений так, что в сети сохраняется регулярный поток данных". Для читателей, занимающихся обработкой сигналов, данный материал проливает свет на то, как применять анализ алгоритмов для разработки архитектуры системы обработки сигналов. Из-за относительно высокой стоимости осуществления соединений в СБИС наибольший эффект дают анализ и классификация параллельных алгоритмов с учетом этих соединений. Алгоритм называется рекурсивным, если в нем повторяются операции одного и того же типа над последовательно поступающими входными данными. В параллельном рекурсивном алгоритме входные и выходные данные снабжаются как пространственными, так и временными индексами. Индекс времени выходных данных всегда на единицу больше индекса входных данных. Пространственные индексы выходных и входных данных связаны регулярным образом. Говорят, что параллельный алгоритм является локально связанным, если пространственные индексы входных данных некоторой рекурсивной операции ограничены наперед заданной величиной. При такой классификации подавляющее большинство алгоритмов обработки сигналов принадлежит к группе локально-рекурсивных. Учитывая общие черты этого класса алгоритмов, можно облегчить проектирование процессорных матриц на СБИС, предназначенных для обработки сигналов. В частности, локальность этих алгоритмов допускает возможность локализовать не только связи, но и управление матрицей процессоров. Более точно это означает, что активизицией всех вычислительных процессоров в структуре можно управлять локально по схеме, подобной схеме потокового вычисления. Понятие потоковых вычислений не является чем-то новым в обработке сигналов. Например, схема таких вычислений естественно возникает при представлении алгоритма БПФ и цифровой фильтрации графами потоков сигналов. Интересно, что дополнительная гибкость локального управления приводит к понятию волнового процессора - локально связанной и самотактируемой (асинхронной) структуре, которая может быть запрограммирована для параллельного выполнения любых локальных рекурсивных алгоритмов. В гл. 7 представлен эволюционный переход от трансверсальной фильтрации к систолической и волновой матричной обработке. Анализ алгоритма и архитектуры сначала рассматривается на примере разработки одномерного БИХ-фильтра и затем распространяется на двумерные систолические и волновые матрицы. В главе делается упор на целостную методологию проектирования систем на СБИС, которая тесно связана с разработкой языков, архитектуры и их практическим использованием. Рассматриваются также преимущества (самотактируемых) управляемых данными вьгчислений и их языковая поддержка при волновом (систолическом) типе программного обеспечения. Для развития параллельных матричных процессов необходим скачок в развитии программного обеспечения и техники автоматизированного проектирования. Для огображгняя параллельных алгоритмов в аппаратуру верхний уровень алгоритмического анализа должен обеспечить мощное абстрактное представление пространственно-временных действий с их естественным параллелизмом, в то время как нижний уровень должен конкретно определять аппаратурное обеспечение. Эта тема обсуждается в гл. 7, в которой вводится понятие H1FI проектирования (иерархическая интерактивная потокографовая интеграция). Такое проектирование включает в себя декомпозицию рекурсивных алгоритмов, абстрактные системы обозначений, по-токографовые (структурные) и функциональные (поведенческие) описания, 128 оцедуры преобразования, обеспечение взаимно однозначного соответствия графических и текстурных кодов и кремниевой компиляции. Для устранения узких мест при реализации высокоскоростных вычислений предлагалось много специализированных архитектур. В таких разработках следует учитывать ряд факторов, влияющих на их полезность и эконо-гмическую эффективность. Особенно важным является достижение компро-.мисса между специализацией и программируемостыо процессорной матрицы, Ш гл. 8 этот вопрос рассматривается вначале с общих позиций, а затем на спе-.циальных примерах. Общее обсуждение охватывает широкий спектр проблем технологии выполнения, применения, алгоритмов, архитектуры, проектирования аппаратуры, систем автоматизации проектирования, циклов из-яотовления и интеграции системы. Для иллюстрации роли упомянутых об-дщих факторов внимание акцентируется на разработке процессорного бло-жа - программируемого систолического кристалла. Для удовлетворения требованиям, предъявляемым различными задача-ми обработки сигналов, желательна и нередко необходима высокая гибкость специализированной архитектуры. Это - программируемость, пере-страиваемость конфигурации, возможность декомпозиции и отказоустойчивость. В гл. 9 представлены высокопараллельный процессор сигналов (РВП-процессор) с перестраиваемой конфигурацией. Он состоит из совокуп-•ности параллельно работающих процессорных элементов, расположенных с регулярными интервалами в двумерной решетке программируемых коммутаторов. Коммутаторы, имеющие локальную память, позволяют динамически объединять массив процессорных элементов в систему с произвольной топологией. В главе демонстрируются гибкость и удобство РВП-процессора в организации вычисления БПФ или общих алгоритмов систолического типа. Очень важно то, что РВП-процессор может быть эффективно реализован на СБИС и благодаря перестраиваемости конфигурации и высокой отказоустойчивости удобен для изготовления на одной полупроводниковой пластине. Системы на СБИС благодаря высокой степени параллелизма могут обеспечить определенную отказоустойчивость, несмотря на наличие дефектов в пластине кремния. В гл. 10 представлены некоторые новые идеи обеспечения отказоустойчивости БИС параллельных матричных процессоров. В ней предлагается подход на основе структурной отказоустойчивости - естественного способа обеспечения отказоустойчивости в локально связанных структурах. В общем случае отказоустойчипость требует введения избыточности в двух формах: увеличение объема оборудования иль увеличение времени вычислений. При использовании СБИС-технологии для выполнения высокопараллельных и отказоустойчивых систем более естественна временная избыточность, на которой основан метод структурной отказоустойчивости. Этот метод как для одномерных, так и для двумерных структур оказывается эффективнее интегральной технологии изготовления процессора на одной полупроводниковой пластине. При проектировании СБИС обычно делается предположение о том, что число портов ввода превышает некоторые характерные размеры входных данных. Однако в реачьных случаях это предположение не всегда выпол- 129 0 ... 17 18 19 20 21 22 23 ... 78
|
