Ссылки на все разделы проекта:

1. Функциональная Потоковая Машина с параллельными вычислениями. Введение (http://tadviser.ru/a/121275)
2. Единая структура данных и программ (http://tadviser.ru/a/149691)
3. Функционирование ФПМ. Выражения языка програмирования (http://tadviser.ru/a/149691)
4. Потоки и их обработка в структуре выражения (http://tadviser.ru/a/150588)
5. Микропрограммирование функций (http://tadviser.ru/a/153069)
6. Программа, как управляемый поток выражений (http://tadviser.ru/a/153069)
7. Макроопределения пользовательских функций(http://tadviser.ru/a/157631)

1. Введение

Цель работы: Создание универсальной ЭВМ параллельно вычисляющей функцию f:

   f(f1,f2,...,fN)    (1-1)

и ее аргументы f1,f2,...,fN - в общем случае также функции с параллельно вычисляемыми аргументами и т.д. вниз по иерархии выражения (1-1)

Сопутствующая и не менее важная цель при этом использование высокоуровневого языка программирования такой ЭВМ на основе выражений (1-1), оперирующих с крупными объектами и, по крайней мере упрощающих, если НЕ снимающих проблему синхронизации параллельно протекающих вычислительных и информационных процессов.

  Безуспешные попытки решения этой проблемы у многих [1] вызвали сомнения в принципиальной и практической ее разрешимости. И все же существует одно из решений, простых настолько, что не просто понять в силу укоренившихся в нашем сознании традиций и образа мышления, ограниченных колеей языков, проложенной автором Fortran’а, искренне пожалевшим о сем при уходе от нас. Для этого пришлось, сохранив принятое lisp единство структуры (и памяти!) данных и выражений - суперпозиций функций, распространить индексирование элементов многомерных матриц на любую древовидную (lisp, tree) структуру, и даже иерархическую, в том числе с циклами.
  На этой основе, объединив (еще унификация) понятия переменной, элементов динамических массивов Jscript (hash языка Perl), выражений языка и даже их макроопределений, пересмотреть традиционные определения переменной, как объекта, устранив отмеченные еще Барроном [2] проблемы, сохраняющиеся даже в L-языках, оперирующих со ссылками. - И все это в рамках подлежащих полному пересмотру организации и управления потоками данных и выражений, включая их синхронизацию и обработку.
  Наконец, пересмотр концепций макрогенерации и микропрограммирования функций, обрабатывающих потоки, а также генерации ими в потоках элементов иерархической структуры по образцу вынудил определить архитектуру ЭВМ (коллектив микро-ЭВМ), зримо динамически (в ходе вычислений) выстраиваемую по структуре вычисляемых выражений и образцов в аналогичные структуры.

  Предлагаемые решения строятся в системе почти естественно принятых концепций:

1.1. Единая структура данных, программ, пространства их памяти и ЭВМ

1) Единая (единственная) гибкая конструкция (1-1) выражений языка программирования – суперпозиция функций, привычная нам со школьных лет, отображающая реализующие ее вычисления (ЭВМ) структуру из микропроцессоров (микро-ЭВМ, транспьюттеров). Каждый из них выполняет параллельно с прочими одну из функций f1, … ,fn, выходы которых связываются со входами функции f, исполняемой также отдельной микро-ЭВМ. В языке отсутствуют какие-либо декларации типа if…then…else, циклы for, while, switch и др.

2) Как и в lisp синтаксически данные имеют все ту же структуру (1-1), в которой теперь f, f1,…,fN могут быть атомами – числами, строками, датами, именами и др.

3) Кодирование структуры (1-1) отличается от принятого в lisp: в самом общем случае она определяется как узел, код которого – пара ссылок:

  УКА – указатель атома f
  УКС – указатель слоя из элементов - узлов f1(...), f2(...),..., fN(...)

Слой - коды его элементов (узлов) размещаются в Блоке (динамически распределяемой ) Памяти (БП), допускающим прямой доступ (индексирование) к узлам по их индексам 0, 1, 2, … в порядке их следования в слое

4) Элемент любого слоя необязательно может получить уникальное в пределах слоя имя, например,
  Bob:f2(...) в (1-1)
наряду с числовым индексом используемое аналогично элементу динамического массива (hash) для доступа к этому элементу.

5) Пространство Area(…) памяти динамически распределяемой под БП слоев и атомов – суть все та же единая структура (1-1). Элемент слоя Area(…) определяется как подпространство - эквивалент определения переменной в традиционном языке. Имя переменной с значениями вида: данные, выражение или макроопределение – суть имя узла слоя Area(…). Впрочем индексируемые (см. далее) элементы одного и того же подпространства могут быть значениями всех перечисленных видов и каждое со структурой (1-1)

6) Синтаксически структура (1-1) является древовидной. Однако использование копий (вторичных) ссылок в пространстве памяти позволяет реализовать иерархическую структуру, выходящую за рамки древовидной и даже со ссылками на верхние уровни (циклы)

7) Мы уже отмечали, что реализующее выражение (1-1) структура взаимосвязанных микро-ЭВМ адекватна структуре этого выражения и поскольку в структуре выражения могут встречаться одинаковые функции, то соответствующую структуру микро-ЭВМ будем определять как Структуру Активаций функций, сокращенно, СА. Потому говоря о потоках на входах (аргументы) и выходах функций, будем, конечно, иметь ввиду эти потоки между соответствующими им микро-ЭВМ в аналогичной структуре СА

1.2. Потоки и концепции управления ими

Безусловно язык разрабатываемой машины должен оперировать с крупными объектами - множествами и еще лучше в движении, а, следовательно, с потоками. И здесь эффективность средств, в основном, определяется двумя факторами:

1) унификация, простота и мощь средств управления потоками, включая сепарацию их элементов- разделение на отдельно обрабатываемые потоки

2) унификация определения потока

1.2.1. Концепции управления потоками

1) Первая и главная концепция состоит в том, что каждый элемент потока снабжается относительно небольшим набором статических свойств, определяемых его структурой, типом атома, кодированием, положением в слое, потоке и др. факторами. Эти свойства сопровождают элемент в потоке и собственно и являются основой для их отбора в отдельные подпотоки или для обработки. С этой целью вводится единая система описания этих свойств и это описание, заключенное в скобки %...% используется также при описании функций, их аргументов и различных элементов лексических единиц языка и данных. Наконец, эти определения могут использоваться как в языке, так и в качестве атомов структуры данных.

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

3) Помимо главного - синтаксически определяемого выхода любой функции можно ввести с уникальными именами любое количество дополнительных выходов функции, стандартным образом для каждого такого выхода определив (анализом свойств) элементы формируемой функцией потока, направляемые на каждый выход. Мало того на каждом таком выходе, как и на основном (с фиксированным именем Out) выходе можно стандартными средствами подключаемого калькулятора (микро-ЭВМ) _Calc обработать полученный на выходе элемент, преобразовать его до выдачи в выходной поток или отказаться от такой выдачи. Дополнительные выходы функции связываются с одноименными каналами (Chanal), объявляемыми на входах других функций и таким образом реальная структура выражения заметно расширяется в сравнении с объявленной (1-1)

4) Входные потоки любой функции могут быть обработаны теми же средствами калькулятора _Calc, что и выходные потоки. И точно также полученный очередной элемент потока может быть преобразован до передачи его функции на обработку или фактически исключен из входного потока. Аналогичными средствами входной поток может быть закрыт (прерван), как и выходной

5) Для входных и формируемых функцией выходных потоков одинаковым образом вводится понятие "Сумматор", отличающийся от числового тем, что может быть не только числом (Суммой), но и иметь любую структуру типа (1-1) и способ ее формирования, определяемый пользователем. Значение этого "Сумматора" можно отправить на выход функции по окончании обработки потока или автоматически (параметр настройки любой функции) получить в указанном подпространстве (переменной). Таким образом создаваемую нами машину можно назвать НЕ просто функциональной потоковой (ФПМ), но и "суммирующей"

P.S. Описанные выше средства управления потоками фактически реализуются вне самих функций включением стандартных примитивов настройки _Calc в качестве "прозрачных" (в любом месте) дополнительных аргументов функции.

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

1.2.2. Унификация определения потоков

Элементами потоков могут быть:

1) Атомы, передаваемые непосредственно между микро-ЭВМ, реализующими конкретные функции в СА

2) Пара ссылок УКА и УКС (R-значение) на соответствующую структуру в Динамически Распределяемой Памяти (ДРП). Указываемая структура может быть как данным, так и выражением. Программа здесь вводится как поток выражений (ссылок на них), к тому же в котором каждое выражение может попутно обрабатывать структуру, синхронно с потоком выражений поступающую из потока данных

3) Целочисленный или Имя-индекс (см. п.1.3)

4) V-значение - пара УКС (а) и индекс (3), определяющий элемент (2) в слое по УКС (а).

V-значение - это то, что отсутствует в любом из существующих языков даже НЕ в потоковом виде и своим отсуствием создает там еще отмеченные Барроном ([2]) проблемы. V-значения позволяет операции типа X:=X+1 выполнять многократно да еще в потоках, не взирая на утверждения [4] о невозможности их повторения (`подстановок` в терминологии авторов [4]) в потоковых ЭВМ. Потому, кроме атомов, индексов и ссылок на элементы структур (R-значения) в ДРП в потоках могут двигаться и V-значения. Более того, большинство генераторов формируют именно поток V-значений.

1.3. Индексирование элементов структуры данных, программ и пространства

  Как обычно, индексирование имеет целью упрощение и сокращение времени доступа к элементам структуры и здесь в отличие от многомерных матриц это осуществляется естественным и зримым образом:

1) Последовательность индексов i,j,…,k в M[i,j,…,k] теперь является потоком и задает путь на древовидной структуре (1-1): В слое подпространства M находится узел с индексом i – его порядковым номером (0, 1, 2, …) в слое , затем в слое этого узла (следующий ниже уровень иерархии) узел с индексом j и т.д. Более того, операция индексирования позволяет выделить все вершины (узлы) пути, а не только конечную. Но главное, этот путь формируется в виде V-значений (п.1.2.2), что дает возможность проконтролировать и даже НЕ только изменить этот путь в процессе индексирования, но и обработать индексируемые по ходу элементы пути, проверить корректность задания индексов и в отсутствие определяемых ими элементов структуры принять решение о ее расширении или приостановке индексирования. Индексируемый элемент может иметь все ту же структуру (1-1).

P.S. Таким образом, формируемый в результате индексирования путь на структуре - все тот же поток, который можно синхронно обработать другим (и НЕ одним!) потоком, например скорректировать атомы элементов (вершин) проходимого в результате индексирования пути. Такого НЕ позволяет ни один из существующих языков и систем программирования

2) В дополнение к безусловно существующему целочисленному индексу элемента любого слоя на любом уровне иерархии структуры (1-1) можно ввести его имя, уникальное в пределах этого слоя. Имя элемента слоя "пространство" - суть имя подпространства. Теперь в M[i,j,…,k] любой индекс i,j,…,k может быть как целочисленным, так и именем элемента в соответствующем слое. Индексируется потоком индексов не только элементы подпространства, но и элементы любой динамически формируемой (вычисляемой) структуры вида (1-1)

3) Выражения допускают привычную для традиционных языков запись операции индексирования в виде M[i,j,…,k], которая автоматически подменяется встроенным макроопределением в обычное (реализуемое связанными микро-ЭВМ) выражение вида (1-1) с генерируемым функциями потоком индексов. При этом собственно подмена исходной записи выражением вида (1-1) НЕ производится: эта подмена реализуется только в структуре СА из микро-ЭВМ

1.4. Обработка структуры потоками в одном выражении ФПМ

Многоуровневую иерархическую структуру (1-1) или ее элементы по горизонали (выборочно элементы слоя) или вниз по уровням иерархии (п.1.3, индексирование) можно обработать потоками данных. Более того, возможно организовать обход обрабатываемой структуры по контуру сверху вниз и слева направо, в процессе которого формировать поток V-значений проходимых вершин. Далее этот поток можно обрабатыватьМихаил Рожков, PARMA TG: Большинство наших BPM-проектов выходят за рамки отдельных процессов и организаций 3 т синхроннно или асинхронно другими потоками или ограничиться сбором статистики и в принципе любой информации по структуре.

1.5. Реализация программы ФПМ

1) Программу - поток выражений (1-1) функций реализует функция $Eval (ядро ФПМ), формирующая для каждого очередного выражения потока аналогичной структуры коллектив микро-ЭВМ - Структуру Активаций (СА) функций и создающая пространство памяти в ДРП с собственными подпространствами. Структура СА может отличаться от структуры вычисляемого выражения за счет как встроенных (п.1.2) макроопределений, так и определяемых пользователем в подпространствах.

2) В реализуемом $Eval (1) выражении может находится другая $Eval, создающая собственное пространство с подпространствами, имена которых могут совпадать с именами отдельных подпространств $Eval (1). В любом случае подпространство, задаваемое в выражении, ищется вначале в исполняющем это выражение $Eval и только в отсутствие такового в $Eval (1) исполняющего выражение с рассматриваемым $Eval и т.д. вверх по иерархии $Eval.

3) Выражения программы (1) выполняются последовательно, однако потоки в каждом из выражений, в основном, обрабатываются параллельно. Точно также организуется параллельная обработка входных и выходных потоков различными экземплярами калькулятора _Calc (п.1.2.1), производимая параллельно с работой самой функции (реализующей ее микро-ЭВМ)

4) В значительной мере эффективность ФПМ достгается совмещением двух уровней программирования - выражений (1-1) с использованием встроенных функций ФПМ (микро-ЭВМ в СА) и микропрограммирования - средств калькулятора _Calc, привлекаемого отдельным экземпляром (микро-ЭВМ) к изменению алгоритма вычислений (действий по умолчанию) наиболее часто используемых функций. В этих случаях калькулятор ограничивается конкретными операциями с отдельным элементом поступившего из входного потока или кортежом синхронно поступивших элементов из различных потоков, и при этом, возможно, с формированием итогов обработки потока (потоков). Обладая большим количеством операций (чем набор функций) язык калькулятора достаточно высок по уровню программирования и, в частности, использует конструкции типа If классических языков и вместе с тем возможности приведения обрабатываемых элементов структуры к нужному виду на основе унифицированного языка описания требуемых свойств согласно п.1.2.1(1), чего НЕТ ни в одном из существующих языков. Наконец, язык программирования _Calc оперирует с параметрами функций (их аргументы) с возможностью их контроля и обработки до запуска функции, обладает целым набором встроенных скоростных регистров, позволяющих обойтись без памяти ДРП. Часть из таких регистров ведется автоматически, отображая характеристики поступившего и обрабатываемого потока, кортежа обрабатываемых значений и др.

5) Собственные ориентированные на класс задач функции, включая генераторы, пользователь вводит в пространстве как макроопределения пользовательских функций в виде выражений (1-1) с использованием калькуляторов _Calc c собственными пользовательскими микропрограммами, с использованием в макроопределениях ранее аналогично введенных им собственных функций (макровызовы или макросы) с их макроопределениями. Вместе с тем удается избежать фактической замены в выражении макровызовов (макросов, пользовательских функций) макрорасширениями на основе макроопределений и связанных с этим потерь времени: к началу вычислений выражения перестраивается соответствующим образом лишь СА (уже без макровызовов). Эти процессы макрогенерации для не находящихся на одном пути макровызовов (в дереве исходного выражения с макровызовами) выполняются параллельно (одновременно) – еще один уровень параллелизма вычислений

Используемая литература

1. В.Г. Хорошевский. Инженерный анализ функционирования вычислительных машин и систем. М., `Радио и связь`, 1987
2. Д. Баррон. Введение в языки программирования, М. `Мир`, 1980
3. В. Жиров. Математическое обеспечение и проектирование структур ЭВМ. М. `Наука`, 1979
4. К. Фути, Н. Судзуки. Языки программирования и схемотехника СБИС, М. `Мир`,1988

Используемые сокращения:

ФПМ	- функциональная потоковая машина
р.5	- раздел 5 проекта ФПМ
п.2.3	- пункт 3 раздела 2
СА	- Структура Активаций – реализующий выражение языка (суперпозицию
 	  функций) коллектив соответствующим образом связанных микро-ЭВМ, 
 	  каждая из которых  реализует отдельную функцию или примитив 
 	 (калькулятор) _Calc
ДРП	- динамически распределяемая память, над которой функуционируют 
 	  микро-ЭВМ СА
БП	- блок ДРП, выделяемый под атом или слой структуры
УКА	- указатель (ссылка на БП) атома (п.2.3)
УКС	- указатель (ссылка на БП)  слоя (р.2)

Смотрите также

• Метод Янова анализа процессов с обратной связью
• Параллельные вычисления коллективом ЭВМ на потоках данных
• Функциональная Потоковая Машина. Программы, Данные и их обработка
• Функциональная потоковая ЭВМ. Примитвы настройки, микропрограммирование
• Функциональная потоковая ЭВМ. Основные функции, программа
• Функциональная Потоковая ЭВМ. Функции пользователя