    
Раздел: Документация
0 ... 30 31 32 33 34 35 36 ... 78 А А-задодц + Арззр -структур + АнесТруктур могут быть использованы для матрично-векторных произведений или в методе сопряженных градиентов. Граница между заполненными и разреженными матрицами определяется экспериментально, как и проектирование систолических процессоров для неструктурированных разреженных матриц. СПИСОК ЛИТЕРАТУРЫ [1] L. М. Adams, "Iterative Algorithms for Large Sparse Linear Systems on Parallel Computers," Ph.D. thesis, Dept. of Appl. Math, and Сотр. Sci., University of Virginia, Nov. 1982. [2] H. M. Ahmed, J. M. Delosme, and M. Morf, "Highly Concurrent Computing Structures for Matrix Arithmetic and Signal Processing," Computer, Jan. 1982, pp. 65-82. [3] A. Bojanczyk, R. P. Brent, and H. T. Kung, "Numerically Stable Solution of Dense Systems of Linear Equations Using Mesh-Connected Processors," Сотр. Sci. Dept., Carnegie-Mellon University, May 1981. To appear in SIAM J. Sci. Stat. Comput. [4] L. Ciminiera, A. Serra, and A. Valenzano, "Fast and Accurate Matrix Triangularization Using an Iterative Structure," Proc. 5th Symp. Comput. Arith., May 1981, pp. 215-221. [5] J. J. Dongarra, F. G. Gustavson, and A. Karp, "Implementing Linear Algebra Algorithms for Dense Matrices on a Vector Pipeline Machine," Math, and Сотр. Sci. Div., Argonne Nat. Lab, Sept. 1982. [6] I. S. Duff, "Full Matrix Techniques in Sparse Gaussian Elimination," in Lecture Notes in Mathematics, Vol. 912: Numerical Analysis, Springer-Verlag, New York, 1981, pp. 71 84. [7] D. Gannon, "A Note on Pipelining a Mesh-Connected Multiprocessor for Finite Element Problems by Nested Dissection," Proc. Int. Conf. Parallel Process 1980, pp. 197-204. [8] W. M. Gentleman and. H. T. Kung, "Matrix Triangularization by Systolic Arrays," SPIE Proc, Vol. 298: Real-Time Signal Processing IV, 1981, pp. 19-26. [9] D. E. Heller, "A Survey of Parallel Algorithms in Numerical Linear Algebra," SIAM Rev., 20:740-777 (1978). [10] D. E. Heller, "Mathematical Hardware-Design Issues and Responsibilities," Purdue Workshop on Algorilhmically-Specialized Computer Organizations, Sept. 1982. [11] D. E. Heller and I. C. F. Ipsen, "Systolic Networks for Orthogonal Decomposition, with Applications," Сотр. Sci. Dept, Pennsylvania State University, Aug. 1981. To appear in SIAM J. Sci. Stat. Comput. [12] D. E. Heller and I. C. F. Ipsen, "Systolic Networks for Orthogonal Equivalence Transformations and Their Applications," Proc. MIT Conf. Adv. Res. VLSI, Jan. 1982, pp. 113-122. [13] К. H. Huang and J. A. Abraham, "Efficient Parallel Algorithms for Processor Arrays," Proc. Int. Conf. Parallel Process., 1982, pp. 271-279. [14] K. Hwang and Y. H. Cheng, "VLSI Computing Structures for Solving Large-Scale Linear Systems of Equations," Proc. Int. Conf. Parallel Process., 1980, pp. 217-227. [15] K. Hwang and Y. H. Cheng, "Partitioned Algorithms and VLSI Structures for Large-scale Matrix Computations," Proc. 5th Symp. Conput. Arith., May 1981, pp. 222-232. [16] L Johnsson, "Computational Anays for Band Matrix Equations," Сотр. Sci. Dept, California Institute of Technology, May 1981. [17] L. Johnsson, "A Computational Array for the QR Method," Proc. MIT Conf. Adv. Res. VLSI, Jan. 1982, pp. 123-129. [18] E. Katona, "Cellular Algorithms for Binary Matrix Operations," Conpar 81, Lecture Notes in Computer Science, Vol. Ill, Springer-Verlag, New York, 1981, pp. 203-216. [19] 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; and in C. A. Mead and L A. Conway, Introduction to VLSI Systems, Addison-Wesley, Reading, Mass, 1980, Sec. 8.3. [20] p. T. Kung and S. Q. Yu, "Integrating High-Performance Special Purpose Devices into a System," SPIE Proc. Vol. 341: Real-Time Signal Processing V, 1982, pp. 17-22. [21] N. K. Madsen, G. H. Rodrigue, and J. I. Karush, "Matrix Multiplication by Diagonals on Vector/Parallel Processors," Inf. Proc. Lett., 5:41-45 (1976). [22] R. W. Priester, H. J. Whitehouse, K. Bromley, and J. B. Clary, "Signal Processing with Systolic Arrays," Proc. Int. Conf. Parallel Process., 1981, pp. 207-215. [23] R. W. Priester, J. H. Whitehouse, K. Bromley, and J. B. Clary, "Problem Adaptation to Systolic Arrays," SPIE Proc, Vol. 298: Real-Time Signal Processing IV, 1981. [24] J. M. Speiser and H. J. Whitehouse, "Parallel Processing Algorithms and Architectures for Real-Time Signal Processing," SPIE Proc, Vol. 298: Real-Time Signal Processing IV, 1981, pp. 2-9. 12 СПЕЦИФИКАЦИЯ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ В ТЕРМИНАХ АППЛИКАТИВНОГО ПРОСТРАНСТВА ДАННЫХ А. Кремерс1, Т. Хиббард2 12.1. ВВЕДЕНИЕ Высокая степень интеграции заставляет программиста использовать параллелизм, скрыто присутствующий в вычислительных задачах. Легкость, с которой большое число обрабатывающих и запоминающих элементов может быть объединено в систему, стимулирует поиск таких алгоритмических решений, при которых большое количество информации обрабатывается параллельно. Повышения эффективности можно ожидать тогда, когда алгоритм подготовлен для сбалансированного распределения вычислений с соблюдением требования локальности (т. е. с помощью коротких линий связи). Поэтому распределение нагрузки и информационного потока является основой разработки алгоритмов для СБИС [8, 13]. В последние годы выяснилось, что многие алгоритмы в различных областях применения вполне подходят для СБИС-реализации. Многие из этих алгоритмов имеют последовательные аналоги, которые, хотя и были из- Дортмундский университет, Дортмунд, ФРГ. 2 Лаборатория реактивного движения, Пасадена, Калифорния. вестны десятки лет, были отвергнуты из-за неэффективности. Пока еще отсутствует общая методология, обеспечивающая проверку способа программирования той или иной вычислительной задачи на СБИС. Из-за высокой стоимости изготовления надежных СБИС и ввиду возрастающей сложности требований к решению практических задач важно позаботиться о тщательном описании алгоритма. Не касаясь вопроса о полезности диаграмм, комментированных примеров и намеков на известные последовательные версии, нужно заметить, что определение СБИС-алгоритма, несомненно, требует точной записи, позволяющей отразить естественный параллелизм алгоритма. Определение алгоритма служит отправным моментом для цикла выполнения СБИС, который начинается с разработки кристалла и заканчивается его тестированием. Кроме того, определение служит основой для внешнего функционального описания устройства. Важным преимуществом точной и адекватной записи параллельного алгоритма является то, что она (реализованная в виде последовательности команд) может быть исполнена и тем самым предоставляет возможность тестирования и диагностики на высоком уровне. Основная цель этой главы состоит в том, чтобы предложить алгоритмическую запись для решения на СБИС, которая во многих случаях может быть более естественной, чем традиционная запись программ. Эта запись основана на понятии пространства данных, введенном авторами несколько лет тому Назад [2, 3] в качестве формальной модели абстрактной машины. Определение пространства данных по природе очень близко к определениям модулей Парнаса [14] я процессов Хорнинга (Horning) иРанделла (Randell) [10]. Подход, основанный на пространстве данных, включает в себя моделирование, ориентированное на управление и на данные, и поэтому может объединить преимущества обоих подходов. В основном пространство данных есть система с изменяемыми состояниями, которые задаются явно на точной информационной основе. Каждый переход из состояния в состояние является функцией всего состояния. Поэтому модель допускает возможность радикального изменения своего состояния за один такт. Последнее является одним из центральных свойств аппликативных систем с изменяемым состоянием, предложенных Бэкусом [!]. Введенные вначале в виде операционной семантической модели программирования пространства данных исследовались с 1979 г. в целях описания программного обеспечения. Был определен большой класс пространства данных с конечной спецификацией и разработан вычислимый синтаксис. Эти пространства данных называются синтаксическими или контекстно свободными. Две версии такого синтаксиса реализованы в языках ПЛ/1 и Паскаль соответственно и успешно использованы как средства описания программ в различных областях применения [7]. Предлагаемая в данной главе запись является аппликативной в том смысле, что во время перехода из состояния в состояние отсутствуют побочные эффекты, влияющие на состояние пространства данных (разд. 12.2). Для целей, преследуемых в этой главе, синтаксис расширен некоторыми новыми понятиями. Во-первых, это понятие подпространства, вводимое для 204 того, чтобы включить вычислительные подструктуры, и, во-вторых, синхронизируемые типы - основные механизмы связи, напоминающие механизмы, введенные в [9]. Следует обратить внимание, что здесь не предлагается новый язык программирования: наша запись алгоритмов не предназначена для непосредственного генерирования кодов и для использования в системе автоматической верификации. Для сохранения простоты записи и проблемной ориентированности мы должны "разделить интересы", однако совершенно ясно, что наши предложения можно развить и в другом направлении (см. [15]). В разд. 12.3 в пространство данных преобразуются два типичных систолических матричных алгоритма: свертки и матричного умножения. В обоих случаях синхронизация является глобальной. В примере со сверткой учтены все детали для конвейерного вывода результата и запуска новой задачи. Во втором примере зти детали опущены, так как они просты и могут быть введены, как и в первом примере. Полная спецификация алгоритма умножения матриц приведена в приложении к этой главе. Раздел 12.4 посвящен локальной синхронизации и некоторым дополнительным конструкциям для ее осуществления. Наконец, в пространство данных преобразуется структура "пузырьковой сортировки" и еще раз демонстрируется матричное умножение. 12.2. ПРОСТРАНСТВО ДАННЫХ И ЗАПИСЬ АЛГОРИТМОВ Прежде чем представить запись алгоритмов, рассмотрим основные аспекты вычислительных моделей, на которых зта запись основана. 12.2.1. Пространство данных Как упоминалось в разд. 12.1, пространство данных (X, &,р) составляется из: 1)переходной системы (X, р), где X обозначает множество состояний и р - частичная функция из X в X; 2)информационной структуры которая представляет собой множество всех функций, определенных на множестве X. Функции, входящие в множество Т, могут быть использованы для получения информации по данному состоянию; однако изменение состояния производится только с помощью функции р. В общем случае предполагается, что 3- дает полное описание каждого данного состояния; тем не менее можно выделить подмножество множества 3-, дающее безызбыточное описание состояний. В [14] исследованы свойства безызбыточных информационных структур. Наряду с формальными отношениями между 3 и X модель пространства данных включает в себя различные аспекты отношений между $ и р. Точнее зто сделано, например, в [5, 6]. В данной главе оставим математическое описание пространства данных в стороне и попытаемся сосредоточиться на описании (спецификации) параллельных алгоритмов. Предлагаем описывать параллельный алгоритм фор- 205 мально в терминах пространства данных. Основными преимуществами этого подхода являются: 1)чувствительность к предыстории вычислительного процесса; 2)функциональный стиль программирования; 3)простой, но мощный механизм связи; 4)выполнимость; 5)диагностика переходов; 6)проблемная ориентация. Набор примеров в последующих разделах иллюстрирует зти свойства. Он включает в себя как простые, так и довольно сложные алгоритмы. Читателю предлагается сравнить полученные описания с их собственными излюбленными точными описаниями в плане перечисленных свойств. 12.2.2. Синтаксис пространства данных Для ограниченного класса пространств данных, который, однако, будет включать в себя пространства данных, встречающиеся на практике, можно дать вычислимый синтаксис. С помощью этого синтаксиса пространство данных может быть определено точно и полно. Синтаксис обладает механизмами для определения вычислительных структур на проблемно-ориентированных уровнях абстракции. Основная идея заключается в аппликативных спецификациях переходов: каждый шаг каждого процесса выполняется путем вычислений выражений без побочного эффекта. Далее приводится краткое и неформальное введение в элементы синтаксиса. Пространство данных определяется следующим: 1)описаниями типа данных, некоторые из которых соответствуют имени ячейки, хранящей соответствующий тип данных; 2)набором функций, одна из которых позволяет определить переходы из состояния в состояние для пространства данных. Типы данных. Примитивными типами данных являются универсальные типы, такие как Boolean, integer, real (sharacter) string и assgts (множество пар имя - значение). Некоторые из этих типов, которые являются встроенными, такие как Boolean, integer, real, не требуют объяснения. Тип string в примерах данной работы не используется, а тип assgts будет объяснен позднее при рассмотрении понятий ячеек и выражений. Определяемые типы получаются путем агрегирования (конкатенации), обобщения (объединения непересекающихся типов) и рекурсии. Все три механизма могут быть использованы в одном и том же определении. Таким образом, в целом определяемые типы составляют однозначную, помеченную, контекстно свободную грамматику со столькими же начальными символами, сколько имеется типов данных. Продукции грамматики имеют вид TYPE T->c.Vi Г, s2T2 ...s„ Тп (п > 0) где с - имя конструктора продукции типа данных Т; хг- -имена селекторов типов Tj в правой части. Для сокращения записи имена типов иногда несут двойную нагрузку: если имя конструктора с не указывается, то мож-206 но использовать имя 7* для типа в левой части конструкции, а если не указывается имя селектора Sj, то можно использовать соответствующий тип Tj для выбора /го компонента правой части выражения. Пример. Множество продукции для типа "двоичное дерево целых чисел" имеет вид TYPE tree-* A root integer left tree right tree □ {empty tree} 11 Как обычно, символ отделяет продукции слева, а символ II завершает список альтернатив. Ячейки. Память описывается списком определений вида CELL Ti HOLD Т2 где Ту, Т2 - типы данных: Тх - тип имени ячейки, Т2 - тип содержимого ячейки. Например, выражение "CELL дерево HOLD целое" означает, что значение типа "дерево" используется для обращения к значениям типа "целое". В случае определимых типов для краткости допускается замена или 7\, или Т2, или обоих типов в представленной схеме объявлений ячейки на их определения. Как уже упоминалось, имеется встроенный тип данных assgts, значениями которого являются множества пар (имя ячейки, содержимое), и каждое множество входит в определение функции (т.е. составные неоднократные появления имен ячеек исключаются). Функции. В дополнение к встроенным функциям, принадлежащим к примитивным типам (например, арифметическим) и упомянутым конструкторам и селекторам, имеются определяемые функции: FUNCTIONF(ti Ti t2T2 ...tn Tn) T = E Типы аргументов Ti задают имена аргументов гг-, которые могут быть использованы в определяющем выражении Е; Т есть тип результата. Определение функции может быть (прямо или косвенно) рекурсивным. Состояние является неявным аргументом каждой определяемой функции. Выражения. Каждое значение примитивного типа, а также каждое имя аргумента есть выражение. В дальнейшем для определения выражений используются следующие правила: 1.Аппликация FEy Е2 ..Еп - обращение к функции F, в качестве аргументов которой используются выражения ЕХ,Е2, . . . ,Еп. Значения аргументов и функции должны иметь типы, соответствующие определению функции. 2.Логическое ветвление IF Е Ei Е2 Значение выражения Е должно быть булевым; значения £\ и Е2 должны иметь одинаковый тип. 207 0 ... 30 31 32 33 34 35 36 ... 78 |
