Раздел: Документация

0 ... 25 26 27 28 29 30 31 ... 78

[9] R. P. Brent and F. T. Luk, "A Systolic Array for the Linear-Time Solution of Tocplitz Systems of Equations," J. VLSI Comput. Syst., Vol. I, No. 1, pp. 1-22,1983. [10] R. P. Brent and F. T. Luk, A Systolic Architecture for the Singular Value Decomposition, Tech. Rep- TR-CS-82-G9, Department of Computer Science, The Australian National University, Aug. 1982.

[11] R. P. Brent and F. T. Luk, A Systolic Architecture for Almost Linear-Time Solution of the Symmetric Eigenvalue Problem, Tech. Rep. TR-CS-82-10, Department of Computer Science, The Australian National University, Aug. 1982. [12] K. Bromlev, J. J. Symanski, J. M. Speiser, and H. J. Whitehouse, "Systolic Array Processor Developments," in H. T. Kung, R. F. Sproull, and G. L. Steele, Jr., eds., VLSI Systems and Computations, Computer Science Department, Carnegie-Mellon University, Computer Science Press, Rockville, Md., Oct. 1981, pp. 273-284. [13] P. R. Cappello and K. Stciglitz, "Digital Signal Processing Applications of Systolic Algorithms," in H. T. Kung, R. F. Sproull, and G. L. Steele, Jr., eds., VLSI Systems and Computations, Computer Science Department, Carnegie-Mellon University, Computer Science Press. Rockville, Md., Oct. 1981, pp. 245-254. [14] H. i. Caulfield, W. T. Rhodes, M. J. Foster, and S. Horvitz, "Optical Implementation of

Systolic Array Processing," Opt. Common ¥0(2):86-9O(Dec, 1981). [15] B. Chazelle, Computational Geometry on a Systolic Chip, Tech. Rep., Computer Science

Department, Carnegie Mellon University, May 1982. [16] D. Cohen and G. Lewicki, "MOSIS-The ARPA Silicon Broker," Proc. 2nd Caltech

Conf. VLSI, California Institute of Technology, Jan. 1981. [17] A. Corry and K. PateL "A CMOS/SOS VLSI Correlator," Proc. 1983 Int. Symp. VLSI

Technol. Syst. Appl, 1983, pp. 134-137. [18] A. L. Fisher, "Systolic Algorithms for Running Order Statistics in Signal and Image Processing," J. Digital Syst., W(2/3):251-264 (Summer/Fall 1982). A preliminary version appears in H. T. Kung, R. F. Sproull, and G. L. Steele, Jr., eds., VLSI Systems and Computations, Computer Science Press, Rockville, Md., 1981. [19] A. L. Fisher and H. T. Kung, "Synchronizing Large Systolic Arrays," Proc. SPIE Symp., Vol. 341: Real-Time Signal Processing V, Society of Photo-optical Instrumentation Engineers, May 1982, pp. 44- 52. A revised version appears in Proc. 10th Int. Symp. Comput. Architecture, June 1983.

[20] A. L. Fisher, H. T. Kung, L. M. Monier, and Y. Dohi, "Architecture of the PSC: A Programmable Systolic Chip," Proc. 10th Int. Symp. Comput. Architecture, June 1983.

[21] A. L. Fisher, H. T. Kung, L. M. Monier, H. Walker, and Y. Dohi, "Design of the PSC: A Programmable Systolic Chip," in R. Bryant, ed., Proceedings of the Third Caltech Conference on Very Large Scale Integration, California Institute of Technology, Computer Science Press, Rockville, Md., Mar. 1983, pp. 287-302.

[22] M. J. Foster and H. T. Kung, "The Design of Special-Purpose VLSI Chips," Computer Л?(1):26-40 (Jan. 1980). A reprint of the paper appears in Digital MOS Integrated Circuits, ed. M. I. Elmasry, IEEE Press Selected Reprint Series, IEEE Press, New York, 1981, pp. 204-217. A preliminary version of the paper entitled "Design of Special-Purpose VLSI Chips: Example and Opinions" also appears in Proc. 7th Int. Symp. Comput. Architecture, La Baule, France, May 1980, pp. 300-307. [23] M. J. Foster and H. T. Kung, " Recognize Regular Languages with Programmable Building-Blocks," J. Digital Syst., 6(4):323~332 (1983). A preliminary version of the paper also appears in VLSI 81, ed. J. P. Gray, Academic Press, London, 1981, pp. 75-84.

p4] E. H. Frank and R. F. Sproull, " Testing and Debugging Custom Integrated Circuits,"

Comput. Sun. /Д4):425 451 (Dec. 1981). f25] W. M. Gentleman and H. T. Kung, "Matrix Triangularization by Systolic Arrays," Proc. SPIE Symp., Vol. 298: Real-Time Signal Processing IV, Society of Photo-optical Instrumentation Engineers, Aug 1981, pp. 19-26. [26] L. J. Guibas and F. M. Li*ng, "Systolic Stacks, Queues, and Counters," Proc. Conf. Adv. Res. VLSI, Massachusetts Institute of Technology, Cambridge, Mass., Jan. 1982, pp. 155-164.

[27] L. J. Guibas. H. T. Kung. and C. D. Thompson, "Direct VLSI Implementation of Combinatorial Algorithms," Proc. Conf. Very Large Scale Integration: Architecture, Design, Fabrication, California Institute of Technology, Jan. 1979, pp. 509-525.

[28] D. E. Heller and I. C. F. Ipsert, "Systolic Networks for Orthogonal Equivalence Transformations and Their Applications," Proc. Conf. Adv. Res. VLSI, Massachusetts institute of Technology, Cambridge, Mass, Ian. 1982, pp. 113-122.

[29] H. T. Kung, "Lets Design Algorithms for VLSI Systems." Proc. Conf. Very Large Scale Integration: Architecture, Design, Fabrication, California Institute of Technology, Jan. 1979, pp. 65-90. Also available as a Caroegie-Mellon University Computer Science Department technical report, Sept. 1979.

[30] H. T. Kung, "The Structure of Parallel Algorithms," in M. C. Yovits, ed., Advances in Computers, Vol. 19, Academic Press, New York, 1980, pp. 65-112.

[31] H. T. Kung, "Special-Purpose Devices for Signal and Image Processing: An Opportunity in VLSI," Proc. SPIE, Vol. 241: Real-Time Signal Processing III, Society of Photo-optical Instrumentation Engineers, July 1980, pp. 76-84.

[32] H. T. Kung, "Use of VLSI in Algebraic Computation: Some Suggestions," in P. S. Wang, ed., Proc. 1981 ACM Symp. Symbolic Algebraic Сотр., ACM SIGSAM, Aug. 1981, pp. 218-222.

[33] H. T. Kung, "Why Systolic Architectures?" IEEE Comput. Mag. 7J(1):37 46 (Jan. 1982).

[34] H. T. Kung, L M. Ruane, and D. W. L. Yen, "Two-Level Pipelined Systolic Array for Multidimensional Convolution," Image Vision Comput., /(l):30-36 (Feb. 1983). A preliminary version appears in VLSI Systems and Compulations, ed. H. T. Kung, G. L. Steele, Jr., and R. F. Sproull, Computer Science Press, Rockville, Md., 1981, pp. 255-264.

[35] H. T. Kung and P. L Lehman, "Systolic (VLSI) Arrays for Relational Database Operations," Proc. ACM-SIGMOD 1980 Int. Conf. Manag. Data, ACM, May 1980, pp. 105-116.

[36] H. T. Kung and С. E. Leiserson, "Systolic Arrays (for VLSI)," in I. S. Duff, and G. W. Stewart, eds.. Sparse Matrix Proceedings 1978, SIAM, Philadelphia, 1979, pp. 256-282. A slightly different version appears in C. A. Mead and L A. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass., 1980, Sec. 8.3. [37] H. T. Kung and R. L. Picard, "Hardware Pipelines for Multi-dimensional Convolution and Resampling," Proceedings of the 1981 IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Management, IEEE Computer Society Press, Nov. 1981, pp. 273-278. [38] H. T. Kung and S. W. Song, "A Systolic 2-D Convolution Chip," in K. Preston, Jr. and L. Uhf, eds., Multicomputer and Image Processing: Algorithms and Programs, Academic Press, New York, 1982, pp. 373-384. An extended abstract appears in Proceedings of 1981 IEEE Computer Society Workshop on Computer Architecture for Pattern Analysis and Image Database Management, Nov. 11-13,1981, pp. 159-160.

---

[39] Н. Т. Kung and S. Q. Yu, "Integrating High-Performance Special-Purpose Devices into a System," Proc. SPIE Symp., Vol. 341: Real-Time Signal Processing V, Society of Photo-optical Instrumentation Engineers, May 1982, pp. 17-22. [40] S. Y. Kung and Y. H. Hu, "Fast and Parallel Algorithms for Solving Toeplitz Systems," Proc. Int. Symp. Mini and Microcomputers in Control and Measurement, San Francisco, May 1981. Also in IEEE Trans. Acoust. Speech Signal Process. Vol. Assp-31, No. 1, Feb! 1983, pp. 66-76.

[41] P. L. Lehman, "A Systolic (VLSI) Array for Processing Simple Relational Queries," in H. T. Kung, R. F. Sproull, and G. L. Steele, Jr., eds, VLSI Systems and Computations, Computer Science Department, Carnegie-Mellon University, Computer Science Press, Rockville, Md, Oct. 1981, pp. 285-295.

[42] С. E. Leiserson, "Systolic Priority Queues," Proc. Conf. Very Large Scale Integration: Architecture, Design, Fabrication, California Institute of Technology, Jan. 1979, pp. 199-214. Also available as a Carnegie-Mellon University Computer Science Department technical report, Apr. 1979.

[43] С. E. Leiserson, "Area-Efficient Graph Layouts (for VLSI)," Proc. 21sl Annu. Symp. Found. Comput. Sci., Oct. 1980, pp. 270-281.

[44] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.

[45] C. A. Mead and L. A. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass, 1980.

[46] T. Nishitani, Y. Kawakami, R. Maruta, and A. Sawai, "LSI Signal Processing Development for Communications Equipment," Proc. ICASSP 80, IEEE Acoustics, Speech and Signal Processing Society, Apr. 1980, pp. 386-389. [47] R. N. Noyce, "Hardware Prospects and Limitations," in M. L. Dertouzos and J. Moses, eds. The Computer Age: A Twenty-Year View, IEEE Press, New York, 1979, pp. 321-337.

[48] T. Ottmann, A. L. Rosenberg, and L. J. Stockmeyer, A Dictionary Machine for VLSI, Tech. Rep. RC 9060 (No. 39615), IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y, 1981.

[49] W. W. Peterson and E. J. Wcldon, Jr., Error-Correcting Codes, MIT Press, Cambridge, Mass, 197Z

[50] C. Savage, "A Systolic Data Structure Chip for Connectivity Problems," in H. T. Kung, R. F. Sproull, and G. L. Steele, Jr., eds, VLSI Systems and Computations, Computer Science Department, Carnegie-Mellon University, Computer Science Press, Rockville, Md, Oct. 1981, pp. 296 300.

[51] A. Sawai, "Programmable LSI Digital Signal Processor Development," in H. T. Kung, R. F. Sproull, and G. L. Steele, Jr., eds, VLSI Systems and Computations, Computer Science Department, Carnegie-Mellon University, Computer Science Press, Rockville, Md, Oct. 1981, pp. 29-40.

[52] R. Schreiber, "Systolic Arrays for Eigenvalue Computation," Proc. SPIE Symp., Vol. 341: Real-Time Signal Processing V, Society of Photo-optical Instrumentation Engineers, May 1982, pp. 27-34.

[53] S. W. Song, "On a High-Performance VLSI Solution to Database Problems," Ph.D.

thesis, Computer Science Department, Carnegie-Mellon University, July 1981. Also

available as a CMU Computer Science Department technical report, Aug. 1981. [54] J. J. Symanski, "A Systolic Array Processor Implementation," Proc. SPIE Symp-, Vol.

298: Real-Time Signal Processing IV, Society of Photo-optical Instrumentation, Aug.

1981.

[55] J- J- Symanski, "Progress on a Systolic Processor Implementation." Proc. SPIE Symp., Vol. 341: Real-Time Signal Processing V, Society of Photo-optical Instrumentation. May 1982, pp. 2-7.

[56] C. D. Thompson, "A Complexity Theory for VLSI," Ph.D. thesis, Carnegie-Mellon University, Computer Science Department, 1980.

[57] M. Tur, J. W. Goodman, B. Moslehi, J. E. Bowers, and H. J. Shaw, "Fiber-Optic Signal Processor with Applications to Matrix-Vector Multiplication and Lattice Filtering," Opt. Lett., 7(9):463165 (Sept. 1982).

[58] U. Weiser and A. Davis, "A Wavefront Notation Tool for VLSI Array Design," in H. T. Kung, R. F. Sproull. and G. L. Steele, Jr., eds, VLSI Systems and Computations, Computer Science Department, Carnegie-Mellon University, Computer Science Press, Rockville, Md, Oct. 1981, pp. 226-234.

[59] R. A. Whiteside, P. G. Hibbard, and N. S. Ostlund, Systolic Algorithms for Monte Carlo Simulations. Draft, Computer Science Department, Carnegie-Mellon University, June 1982.

[60] M. Yano, K. Inoue, and T. Senba, "A LSI Digital Signal Processor," Proc. ICASSP 82, IEEE Acoustics, Speech and Signal Processing Society, May 1982, pp. 1073-1076.

[61] D. W. L. Yen and A. V. Kulkarni, "Systolic Processing and an Implementation for Signal and Image Processing," IEEE Trans. Comput., C-.?/(10):100CM009 (Oct. 1982).

9

РОЛЬ ВЫСОКОПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЕЙ С ПЕРЕСТРАИВАЕМОЙ КОНФИГУРАЦИЕЙ В ОБРАБОТКЕ СИГНАЛОВ

Л. Сшйдер1 9.1. ВВЕДЕНИЕ

Несмотря на то, что микрокомпьютер является универсальным устройством, его часто используют совместно с ПЗУ в качестве специализированного устройства последовательного типа. Целесообразность такого применения обусловлена тем, что специализация уже разработанного, проверенного и серийно выпускаемого микрокомпьютера требует лишь программирования ПЗУ, а эта задача легче трудоемкого схемного проектирования.

В качестве высокопараллельной системы обработки сигналов может выступать вычислитель (высокопараллельный) с перестраиваемой конфигурацией (ВППК-процессор). В качестве устройств обработки ВППК-ироцессоры могут изготавливаться независимо от области применения, а совершенствоваться и изменяться с соответствующим программированием. Вследствие своих архитектурных характеристик они являются отказоустойчивыми устройствами, удобными для интегрального исполнения. Наконец, если

---

практические соображения диктуют исполнение процессора сигналов в виде СБИС, то реализация ВППК-процессора может служить первым шагом к системному проектированию [1].

9.2. ВППК-ПРОЦЕССОР

Архитектура семейства ВППК-процессоров уже была описана, например в [2, 3]; здесь напомним ее основные особенности, прежде чем перейти к рассмотрению примера. Основным компонентом ВППК-процессора является коммутационная матрица: совокупность процессорных элементов (ПЭ), соединенных через регулярные интервалы с сетью программируемых коммутаторов (рис. 9.1). Процессорные элементы представляют собой микропроцессоры с локальной памятью программ и данных и собственными программными счетчиками; общая программная память отсутствует, и все ПЭ работают синхронно. Непосредственная связь между процессорными элементами отсутствует, каждый из них соединен с небольшим числом (обычно восемь) соседних коммутаторов. Число коммутаторов, подключенных к ПЭ, ширина линий передачи данных и т.д. являются параметрами, характеризующими ВППК-процессоры различных типов.

Коммутаторы, каждый из которых снабжен локальной памятью небольшого объема, являются программируемыми. Под управлением команды, называемой установкой конфигурации, коммутатор соединяет две или более линии передачи данных. Статическое соединение двух ПЭ устанавливается соответствующим программированием цепочки промежуточных коммутаторов. Таким образом, осуществляется, скорее, коммутация каналов, чем коммутация пакетов. Она осуществляется глобально управляющей ЭВМ так, что ПЭ не должны содержать информацию о том, с чем они связаны; они просто считывают данные или записывают их в свои локальные порты, а поток данных определяется структурой взаимосвязи ПЭ, запрограм-

Рис 9.1. Две процессорные матрицы: квадратами показаны ПЭ; кружками препставле ны коммутаторы; линии означают пути данных. Масштаб рикоГнарушеТ пГ шадь ПЭ значительно больше площади коммутаторовРУ ~ °"

	1.1		2.1		3.1	-
						-э>-

	1Л		2М		ЗА	-

Рис. 9.2. Граф связи для восьмиточечного алгоритма БПФ

мированной в коммутаторах. Допускаются пересечение и разветвление линий передачи данных. Коммутаторы, расположенные по периметру решетки, связаны с внешним оборудованием.

Две коммутационные матрицы, показанные на рис. 9.1, различаются шириной коридора - параметром, характеризующим число коммутаторов, разделяющих соседние ПЭ. Ширина коридора - важный параметр, оказывающий существенное влияние на удобство программирования структуры связей ПЭ: чем шире коридор, тем больше существует различных путей для предотвращения перегрузки сети при программировании алгоритмов, описываемых сложными графами [3].

Пример. Обычно параллельные алгоритмы, в частности алгоритмы обработки сигналов, представляются в виде графов, каждая вершина которых соответствует одному из множеств процессов. Граф описывает структуру связи процессов, а процессы определяют вычисления в каждом элементе структуры. В качестве примера рассмотрим алгоритм восьмиточечного БПФ, граф которого представлен на рис. 9.2 [4], Всем вершинам графа соответствуют идентичные процессы:

read В, В; С <-В +QB: С write С, С;

- QB

где Q - константа.

Представим алгоритм в конвейерном виде, вставляя команду предшествующего процесса в цикл.

Поскольку представление параллельного алгоритма состоит из Двух частей: графа и множества соответствующих процессов, то программирование ВППК-процессора также состоит из двух этапов: отображение графа на коммутационную матрицу и программирование ПЭ. На рис. 9.3 показано прямое отображение графа БПФ на матрицу, приведенную на рис. 9.1,6. Для предотвращения перегрузки перекрестных линий связи в центре матрицы необходим двойной коридор. После отображения графа на коммутационную матрицу соединение процессоров осуществляется автоматически. (В данном примере это не столь существенно, поскольку все ПЭ выполняют одни и те же коман-

0 ... 25 26 27 28 29 30 31 ... 78