    
Раздел: Документация
0 ... 33 34 35 36 37 38 39 ... 78 FUNCTION CJNIT (N INTEGER) ASSGTS = : LET CNN =. 0.0 CJNITJHELP N - N 1 IF > N 1 CJNIT - N 1 SKIP : OMEGA TEST REF STEP FETCH : A FUNC REF К REF N 1 1 BJ4JNC REF К REF N 1 1 LET STEP = EXECUTE : EXECUTE : CFUNC REF К REF N 1 1 IF = REF К - * 3 REF N 2 LET STEP - STOP : LET К = + REF К 1 LET STEP = FETCH : STOP SKIP : LOAD 1 LET К LET N = CJNIT 3 LET A IN LET AJN LET AJN LET BJN LET BJN LET BJN LET STEP = , 1.0 . 2.0 , 1.0 = . 2.0 = . 2.0 = , 3.0 = . 4.0 = . 5.0 FETCH 2.0 . 1.0 1.0 . 2.0 4.0 . 5.0 5.0 . 3.0 3.0 , 4.0 (K. = 1.) (.N:=3.) (.C33:= +OOOOOOE + 00.) (C23 = + 0.00O0OE+00.) (.C32:= +0.O0O00E + 00.) (.C13:= +0.00000E + 0O) (.C31:= +O.0000OE + 00.) (C22: = + 0. OOOOOE + 00.) (CI 2: = +0.00000E + 0O.) (C21: = +0.00000E+00.) (.C11: = + 0.00000E + 00.) (.AJN1: = . + 1.OOOOOE+ 00, (AJN2: = ,+2.00000E + 00. (.AJN3: = , + 2.00000E +00. (B IN1: = , + 3.OOO00E + OO, (. В J N2: =, + 4.00000E + 00, (B IN3: = , + 5 00000E + 00, (STEP: = FETCH.) + 2.00000E + 00, +1 .OOOOOE + 00.) + 2.00000E + 00, +1 .OOOOOE + 00..) + 1.00000E + 00. + 2.00000E + 00..) +4.00000E + 00, + 5.00000E + 00.) + 5.00000E + 00, + 3. OOOOOE + 00..) + 3.00000E + 00, +4.00000E +00.) (A11:= +1.OOOOOE+ 00.) (. A l N1: =, + 2.00000E + 00, + 1 OOOOOE + 00..) (B11.= +3.00000E + 00.) (. B l N1: =, + 4. OOOOOE + 00, + 5. OOOOOE + 00..) (.A11:=+1.00000E + 00.) (.AJN1: = ..) (.A12:= +2.00000E + 00.) (A13:= +1.OOOOOE+ 00.) (.A21:= + 2.00000E + 00.) (.AJN2:=. + 1.OOOOOE+ 00..) (.A22: = +2.00000E +00.) (A31:= +2.00000E + 00.) (AJN3: = , +1 .OOOOOE + 00, + 2.00000E + 00..) (.B11:= +5.00000E + 00.) (.BJN1: = .) (.B12:= +5.00000E + 00.) (,BJN2: = , + 3.00000E + 00.) (.B13:= +5.00000E + 00.) (. В JN3: =. + 3.00000E + 00, + 4.00000E + 00.) (B21: = +4.00000E +00.) (B22:=+4.00000E + 00.) (B31:= + 3.00000E + 00.) (STEP: = EXECUTE.) (.C11: = +1.59999E + 01.) (C12:= +1.39999E + 01.) (C13:= +5.00000E + 00.) (.C21:= +1.39999E + 01.) (C22:= +8.00000E + 00.) (C31:=+6.00000E + 00.) (,K:=4.) (STEP: = FETCH.) (.C11:= +3.00000E + 00.) (K: = 2.) (STEP: = FETCH.) - ► > » (,A11: = + 2.00000E+00.) (AJN 1: =, +1 .OOOOOE + 00.) (,A12: =+1.OOOOOE+ 00.) (A21:= + 2.00000E + 00.) (AJN2: = . +2.00000E + 00, +1 OOOOOE+ 00 .) (,B11:=+4.00000E + 00.) (BJN1: = , + 5.0000QE + 00..) (.B12:= +4.00000E + 00.) (B J N2: =, + 5.00000E + 00, + 3.00000E + 00..) ( B21:= +3.00000E + 00.) (STEP: = EXECUTE.) -* + -► (.C11: = +1.09999E + 01.) (.C12:= +4.00000E + 00.) (.C21:= +6.00000E + 00.) (.K: = 3.) (.STEP: = FETCH.) (.А12: = +1. OOOOOE + 00.) (.А13:= +2.00000Е + 00.) (.А21: = +1.OOOOOE+ 00.) (.A IN2: = ..) (.А22:= + 2.00000Е + 00.) (.А23.= +2.00000Е + 00.) (.А31: = +1.OOOOOE+ 00.) ( A IN3: = , + 2.00000E + 00.) (А32: = +2.00000Е + 00.) (В12: = +3.00000Е + 00.) (B IN2: = .) (.В13:= +3.00000E+00.) (.BJN3: = .+4.00000E + 00..) (.В21:= + 5.00000Е + 00.) (В22:= +5.00000Е + 00.) (.В23.= +5.00000Е + 00.) (В31: = + 4.00000Е + 00.) (В32: = +4.00000Е+00.) (STEP: = EXECUTE.) (С12: = + 1.69999Е + 01.) (.С13:= +1.09999Е + 01.) (С21:= +1.89999Е + 01.) (С22:= +1.79999Е + 01.) (.С23:= +1.OOOOOE+01.) (.С31:= +1.OOOOOE+ 01.) (.С32:= +8.00000Е + 00.) (К: = 5.) ( STEP: = FETCH.) (А13:= +1.OOOOOE+ 00.) (.А22:= +1.OOOOOE+00.) (.А23: = +2.00000Е + 00.) (А31:= +2.OOOOOE+ 00.) (AJN3: = ..) (.А32:= +1.OOOOOE+ 00.) (А33:= +2.00000Е + 00.) (В13:= +4.00000Е + 00.) (B IN3: = ..) (.В22:= +З.О0000Е + 00.) (.В23:= + 3.00000Е + 00.) (.В31:= +5.00000Е + 00.) (В32:= + 5.00000Е + 00.) (В33:= +5.00000Е + 00.) (STEP: = EXECUTE.) (С13:= +1.50000Е + 01.) (С22:=+2.09999Е + 01.) (С23:= +1.59999Е + 01.) (.С31.= +2.00000Е + 01.) (.С32:= +1.29999Е + 01.) (С33:= +1.OOOOOE+ 01.) (К: = 6.) (А23 (А32 (.АЗЗ (.В23 (В32 (.ВЗЗ = +1.OOOOOE+ 00.) = +2.00000Е + 00.) = +1.OOOOOE+00.) = +4.00000Е + 00.) = +3.00000Е + 00.) = +3.00000Е + 00.) (STEP: = EXECUTE.) (С23:= +2.00000Е+00.) (С32:= +1.89999Е + 01.) (.С33:= +1.29999Е + 01.) (К: = 7.) (STEP: = FETCH.) - > ► -> (А33:= +2.00000Е + 00.) (В33:= +4.00000Е + 00.) ( STEP: = EXECUTE.) (СЗЗ: = + 2.09999Е + 01.) (STEP: = STOP.) СПИСОК ЛИТЕРАТУРЫ [1] J. Backus, "Can Programming Be Liberated from the Von Neumann Style? A Functional Style and Its Algebra of Programs," Commun. ACM, 27:613-641 (Aug. 1978). [2] A. B. Cremers and T. N. Hibbard, "Formal Modeling of Virtual Machines," IEEE Trans. Software Eng., 4:426-136 (1978). [3] A. B. Cremers and T. N. Hibbard. "Functional Behavior in Data Spaces," Inf-Forschungsber., No. 37/77, Universitat Dortmund; y4cta Inf., 9:293-307,1978. [4] A. B. Cremers and T. N. Hibbard, "Orthogonality of Information Structures," Inf.-Forschungsber., No. 31/76, Universitat Dortmund; Acta Inf, 9:243-261 (1978). [5] A. B, Cremers and T. N. Hibbard, "On the Formal Definition of Dependencies between the Control and Information Structure of a Data Space," Theor. Comput. Sci., 5:113-128(1977). [6] A. B. Cremers and T. N. Hibbard, "Data Spaces with Indirect Addressing," Inf-Forschungsber., No. 43/77, Universitat Dortmund; Mjath. Syst. Theory, /2:151-173 (1978). [7] A. B. Cremers and T. N. Hibbard, "Specification of Data Spaces by Means of Context-Free Grammar-Controlled Primitive Recursion," Inf.-Forschungsber., No. 107/80, Universitat Dortmund (1980). [8] L. S. Haynes, R. L. Lau, D. P. Siewiorek, and D. W. Mizell, "A Survey of Highly Parallel Computing," IEEE Comput., Jan. 1982, pp. 9-24. [9] C. A. R. Hoare, "Communicating Sequential Processes," Commun. ACM, 21:66&-6П (1978). [10] J. J. Horning and B. Randell, "Process Structuring," ACM Comput. Surv., 5:5-30 (1973). [11] Н. Т. Kung, "Why Systolic Architectures?" IEEE Comput., /5(l):37-46(Jan. 1982). fl2] S. Y. Kung, K. S. Arun, R. J. Gal-Ezer, and D. V. Bhaskar Rao, "Wavefront Array Processor: Language, Architecture, and Applications," IEEE Trans. Co,nput.„ C- J/(11):1054-1066 (Nov. 1982). fl3] С Mead and L. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass., 1980. [14j D. L. Parnas, "A Technique for Software Module Specification with Examples," Common. ACM, /5:330-336(1972). 14 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ В ТЕРМИНАХ ПРОСТРАНСТВЕННО-ВРЕМЕННЫХ РЕКУРРЕНТНЫХ УРАВНЕНИЙ М. Чей, К. Мид1 13.1. ВВЕДЕНИЕ Современный уровень развития технологии изготовления СБИС сделал возможным создание вычислительных систем, содержащих многие сотни тысяч транзисторов. Интерес при проектировании должен состоять в достижении высокой вычислительной сложности, а не просто в объединении огромного числа одинаковых простых компонентов, таких как элементы памяти. Проектируемая система может быть представлена как совокупность объектов исполняющей среды (например, транзисторов в СБИС-технологии) или как иерархическая система, в которой обьекты каждого уровня строятся из объектов нижнего по отношению к данному уровню. Первое представление позволяет выполнять всю разработку из обьектов основного (нижнего) уровня. Такое представление может оказаться подходящим дня машинного исполнения, но оно неудобно для разработки, а стоимость проверки функционирования разработанной системы и ее физической ком ионовки велика. С ростом сложности разработки недостатки этого подхода становятся более очевидными. Цель второго подхода, основанного на иерар хичсском методе проектирования [11], состоит в управлении сложностью разработки путем правильного разбиения объектов каждого уровня на под системы. 13.1.1. Иерархическое проектирование Предположим, что требуется вычислить произведение матриц; для этого существует много способов. Одним из возможных способов реализации этой функции является алгоритм [8], показанный на рис. 13.1. Элементарный блок (элемент) имеет три входа и три выхода; каждый элемент выполняет операции aBhtx=mBXXbBX+aBX; твьк=твх, ЬВЬ1Х=6ВХ. Поскольку 1 Калифорнийский технологический институт, Пасадена, Калиф. 224  Рис. 13.1. Систолический алгоритм ьвх-твх-МР- f разряд V,-Ч>2- -аць/х ьвых • Щых -MP Рис. 13.2. Конвейеризованный алгоритм при разработке и обосновании систолического алгоритма используется только упомянутое описание каждого элемента, их физическую реализацию можно пока не рассматривать. При обсуждении производительности или сложности данного алгоритма можно также обойтись без знания фактических параметров каждого элемента. После окончания проектирования данного алгоритма, т.е. после того, как проверено, что он является корректным и удовлетворяет требованиям по производительности, можно осуществлять дальнейшие действия, концентрируя внимание на разработке каждого конкретного элемента. Такой элемент может быть выполнен как элемент с последовательной обработкой каждого разряда двоичного числа или как оперирующий параллельными словами, представляющими собой двоичные числа. Одна из возможных схем реализации элемента с поразрядной последовательной обработкой показана на рис. 13.2 [9, 18]; три последовательности разрядов поступают на входы конвейера, а результирующие последовательности появ- 0 ... 33 34 35 36 37 38 39 ... 78 |
