Система потоковой обработки информации с интерпретацией функциональных языков Советский патент 1991 года по МПК G06F15/16 

Изобретение относится к вычислительной технике и может быть применено при построении ЭВМ различного назначения, в том числе и персональных ЭВМ.

Целью изобретения является повышение быстродействия и расширение функциональных возможностей системы.

На чертеже приведена схема системы.

Система содержит блок 1 выходного интерфейса, операционное устройство 2,блок 3 хранения структур данных, блок 4 хранения подпрограмм функциональных форм, блок 5 хранения подпрограмм элементарных функций, блок 6 хранения программ,

блок 7 хранения редуцируемых пакетов, блок 8 редукции пакетов, блок 9 хранения имен данных, блок 10 хранения исполняемых пакетов, блок 11 обработки пакетов, блок входного интерфейса 12, внешнюю магистраль 13 и ЭВМ 14 загрузки, которая своими входом 15 и выходом 16 подключена к внешней магистрали 13, с которой соединены первый выход 17 блока 1 выходного интерфейса и выход 18 блока 12 входного интерфейса, выход 19 данных блока 12 соединен с входом 20 данных блока 3 хранения структур данных, выход 21 данных которого подключен к первому информационному входу 22 операционного устройства 2, выО

о

VI О 00

код 23 которого подключен к первому информационному входу 24 блока 1 выходного интерфейса, выход 25 профамм блока 12 входного интерфейсе, подключенный к входу программ 26 блоке б хранения программ, выход 27 начального пакета блока 12, соединенный с входом 28 начального пакета блока 7 хранения редуцируемых пакетов, выход 29 подпрограмм функциональных Форм блока 12, подключенный к одноименному входу 30 блока 4 хранения подпрограмм функциональных форм, выход 31 подпрограмм элементарных функций блока i2, подключенный к одноименному входу 32 блока 5 хранения элементарных функций, вход 33 кода имени элементарных функций которого соединен с одноименным выходом 34 бпока 11 обработки пакетов, а выход 35 подпрограмм подключен к входу 36 подпрограммы этого же блока 11, выход 37 управления которого соединен с входом 38 управления операционного устройства 2, йыход 39 чтения блока 11 обработки пакетов, подключенный к входу 40 чтения блока 3 хранения структур данных, выход 41 данных для внешней магистрали которого подключен к одноименному входу 42 блока 1 выходного интерфейса, второй выход 43 которого соединен с входом 44 результата блока 6 хранения программ, а его третий выход 45 подключен к входу 46 результата блока 3 хранения структур данных, выход 47 имени блока данных которого подключен к входу 48 имени блока данных блока 9 хранения имен данных, выход 49 готовности блока 6 хранения программ, соединенный : входом 50 готовности блока 7 хранения редуцируемых пакетов, вход 51 неготового п, - кета которого подключен к выходу 52 неготового пакета блока 8 редукции пакетов, выход 53 исполняемого пакета которого соединен с входом 54 исполняемого пакета блока 10 хранения исполняемых пакетов, вход 55 имени первого аргумента блока 9 хранения имен данных, подключенный к выходу 56 имени первого аргумента блока 10 хранения исполняемых пакетов, вход 57 нового имени и вход 58 готовности аргумента которого соединены соответственно с одноименными выходами 59 и 60 блока 9 хранения имен данных, выход 61 начального пакета блока 7 хранения редуцируемых пакетов, подключенный к одноименному входу 62 блока 8 редукции пакетов, вход 63 фрагмента записи которого подключен к одноименному выходу 64 блока 6 хранения программ, вход 65 запроса программ которого соединен с выходом 66 запроса программ блока 8 редукции пакетов, выход 67 запроса подпрогэаммы функциональных

форм которого подключен к одноименному входу 68 блока 4 хранения подпрограмм функциональных форм, выход 69 которого соединен с входом 70 подпрограммы блока

8 редукции пакетов, выход 71 готового пакета блока 10 хранения исполняемых пакетов, соединенный с одноименным входом 72 блока 11 обработки пакетов.

Система ориентирована на обработку

0 данных в режиме интерпретации записи алгоритмов обработки на функциональных языках. Интерпретируемые функциональные языки состоят из следующих основных компонент: набора элементарных функций,

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

0 элементарных средствами функциональных форм.

Данные в системе представляются словами фиксированной разрядности, состоящими из двух полей: поля тегов и поля

5 информации (например, поле тегов 16 разрядов и поле информации 32 разряда). Данные организуются в массивы, имеющие определенную структуру. Элементарные функции определяются над

0 массивами. Доступ к массивам осуществляется по именам.

Управляющая информация представляется в виде пакетов. Пакет представляет собой запись, состоящую из следующих

5 полей: имя первого аргумента, имя второго аргумента, имя функции, имя результата, поле управляющих флагов,(например, именные поля по 16 разрядов и поле флагов 8 разрядов - всего 72 разряда).

Q Работа системы основана на аппаратной интерпретации функциональных языков, порождении графа программы в режиме редуцирования функциональных записей и исполнении графа программы в

5 режиме управления потоком данных. При этом все указанные процедуры совмещены во времени и согласованы по скорости выполнения.

Базовые операции функционального

g языка и базовые структуры данных реализованы микропрограммно в соответствующих устройствах системы и в широком диапазоне представления: от элементарных арифметических операций над скалярами до

5 крупных функциональных операторов над блоками данных, имеющих структуры векторов, матриц, списков и т.п, Архитектура системы построена так, что она позволяет осуществлять одновременное порождение процесса и его выполнение в виде потока

пакетов с текущим уничтожением обработанных и ненужных пакетов. При этом пакеты преимущественно инициируют перемещения крупных блоков данных и выполнение крупных функциональных операций над ними.

Принятая организация процесса соответствует структуре функционального языка и создает условия для его эффективной реализации.

Инициализация системы состоит из трех фаз: загрузки интерпретатора, загрузки программы и данных, занесения начального пакета.

Загрузку интерпретатора системы осуществляют с помощью ЭВМ загрузки через внешнюю магистраль 13 путем записи программы выполнения элементарных функций и подпрограмм реализации порождающих редукций, соответствующих функциональным фор мам. Загрузку осуществляют в блоки 4 и 5 по входам 30 и 32 соответственно через блок 12 входного интерфейса. В блок 4 также загружают библиотеку используемых функций.

По сигналу Сброс, проходящему с внешней магистрали 13 (цепи сброса не изображены), память блоков 3, 6-11 и регистры операционного устройства 2 обнуляются.

В блок 6 хранения программ по входу 26 по внешней магистрали 13 через блок 12 входного интерфейса в режиме пословной передачи информации поступает программа (или набор программ), представляющая собой последовательность символов функционального языка. При этом ЭВМ 14 загрузки предварительно осуществляют компиляцию записи, размечая ее на блоки и присваивая метки, необходимые для связывания полей редуцируемых пакетов с фрагментами и блоками функциональных записей.

В блок 3 хранения структур данных по входу 20 с внешней магистрали 13 через блок 12 входного интерфейса в режиме пословной передачи информации поступают структурированные блоки данных, представляющие собой векторы, матрицы, мно- гомерные массивы, списки и т.п., обозначенные определенным именем и оформленные в виде последовательностей слов описанного формата. Одновременно с приемом и размещением данных в блоке 3 происходит выделение и передача имени блока данных с выхода 47 блока 3 на вход 48 блока 9 хранения имен данных, который запоминает имена всех данных, размещенных в блоке 3.

Для инициализации процесса обработки информации в блок 7 хранения редуцируемых пакетов по входу 28 из внешней магистрали 13 через блок 12 входного ин- 5 терфейса загружают начальный пакет, который имеет структуру полей, описанную выше. Редуцируемые пакеты отличаются от исполняемых пакетов тем, что в их именных полях содержатся ссылки на функциональ0 ные формы и функциональные записи. Для распознавания характера ссылок служат соответствующие флаги.

Блок 7 хранения редуцируемых пакетов принимает также по своему входу 50 с выхо5 да 49 блока 6 сообщения, которые используются для определения готовности пакетов к выполнению операции редукции. Готовый к редуцированию начальный пакет с выхода 61 блока 7 поступает по входу 62 в блок 8

0 редукции пакетов. Блок 8 расшифровывает поля пакета, в результате чего с выхода 66 блока 8 на выход 65 блока 6 поступают сигналы запроса на требуемый фрагмент записи, а с выхода 67 на вход 68 блока 4 5 сигналы запроса на требуемую подпрограмму функциональной формы. Фрагмент записи с выхода 64 блока 6 и требуемая подпрограмма с выхода 69 блока 4 поступают в блок 8 редукции пакетов по соответст0 вующим входам 63 и 70 этого блока. В результате выполнения редукции исходный пакет, занесенный в блок 7, уничтожается и заменяется одним или несколькими результирующими. При этом блок 8 определяет

5 тип полученных результирующих пакетов. Если пакет является редуцируемым, он может быть готовым или неготовым к редуцированию. Готовый пакет используется как исходный для выполнения следующего шА0 га редукции. Неготовый пакет с выхода 52 блока 8 редукции пакетов поступает на вход 51 блока 7, который переводит его в готовый пакет по приходу соответствующего сообщения на вход 50 из блока 6. Результирую5 щий пакет считается исполняемым, если он содержит ссылки только на элементарные функции и данные, являющиеся аргументами элементарных функций. Исполняемый пакет с выхода 53 блока 8 редукции пакетов

Q поступает по входу 54 в блок 10 хранения исполняемых пакетов, где запоминается. Таким образом, результатом совместного функционирования блоков 4 и 6-8 является поток исполняемых пакетов, образующих

5 граф траектории вычислительного процесса. Блок 10 хранения исполняемых пакетов, принимая пакеты из блока 8 по входу 54, определяет готовность данных, являющихся аргументами принятого пакета. С этой целью имя первого аргумента поступает с

выхода 56 блока 10 на вход 55 блока Ј хранения имен данных, ц пугай ассоциативного-поиска блок 9 определяет налмчиз запрошенных данных i блснг-з 3 хйвненнп структур данных. Пру нэ/шчии запрошенного имени в блоке 9 на его пыксда 60 пияалп- ется сигнал отклика, который поступает из вход 58 блока 10 хранения пккетоз и заводит флаг готовности аргумента. При отсутствии сигнала отклика соответствующий флаг |не взводится. А налоп чнгн ггроидаурн ОЛНЯеТСЯ ДЛЯ ОПреДвЛе - -.) ГСТСБ ЗСТИ ЭТО

рого аргумента, Далее блок 10ог:у|пеег:- лпэт ;энализ„готовности данных по состоян -о .|флагов. Если аргументы готовы, пакптзаио- |сится в очередь готовых к обработке пакч- |тов, размещаемых во анутранж-н помлш блока 10. Если аргументы по готонн, пакет заносится в очередг пакетов, о;- идйЮ1.ци прихода данных, которая тпюхе рзлмещекй п другой внутренней памяти :ичжа 10.

При поступлении но У УХ данных г. блок Охранения структур данных м еоотпетстБ-эн- но занесении новых имен и блок 9 происходит пересылка каждого иово х; имени г. выхода 59 блока 9 в блрк 1Q чепаз соотвегСТВуЮЩИЙ ВХОД 57 Где ПРОИСХОДИТ СраганГ;ние нового имени с мменвмь- эргу::/;е1Тгоп пакетов, ожидающих прихода данных, Пш-- iix совпадении взводится соот зетгг ующ флаг готовности данных, Состояния флзгоь готовности данных з пзквто.х, ожидают.:1:.--: прихода данных, англизируются постоянно ;и в момент выполнения условий гстовноо всех аргументов конкретного пакета ofi переносится в очередь готовых пикетов, Гете-- зые пакеты с выхода 7 i блок;; 10 р-знеп ::- исполняемых пакетов поступают чср вход 72 в блок 11 обработки п-нхетоз.

Блок 11 обработки пакетов помн 1мз:;т готовый пакет блока 10 и ооущеотвяя - расшифровку его полей сти, определяемой его программами ропрограммами), рэсполсхженныгп на блоке, Блок 11 выраЁзть ;1аетсигнн. аргументов, сопровождаемы г.иг} -йлом чтя- ния; которые с выхода 39 поступают ;;; аход 40 блока 3 хранения структур данных, который осуществляет поиск us пес шейных w.sc- сивов и их пересылку с зьшздз /1 Ьлсяхз 3 на выход 22 операционного у:;трой; .1аа 2, Одновременно код имени зле.ментар -юй фч-чо ции с выхода 34 блока 11 лссгунво- по ;x:i; :y 33 в блок 5 хранения подпрограмм;- але. - тарных функций. Блок бопущесгв/нют пс;1;:;; запрошенной подпрогршима и пересылает ее с выхода 35 в 6ло: 11 обэаЗггпси нчкетор, который преобразует получа гпую подпрограмму в последователы-11 ст :, управля оиг/ :; слов и сигналов, поасдэваемых и onepau.i.rонное устройство 2 с выходе 37 блока 11 на вход 38 блока 2. По завершении обработки данных п операционном устройстве с выхода 23 блока 2 на вход 24 блока 1 поступают w.-jw результате., сопровождаемое сигналом . а так:ке результат выполнения операций. Для этого блок 11 формирует и передзет с выхода 37 на вход 38 операционного устройс мза 2 соответствующие команды, С выход ; 45 блока 1 выходного интерфейса результат вьполнбими операции и имя ре- ;)ул ;тэта поступают по входу 46 в блок 3. В бж гя 3 npuFfiTbic-i данные размещают под Кглс чем,указанным а пакете. Результаты обработки данных в операционном устройстве ).. могут быть также переданы с выхода 23 этого блока -зрез блок 1 ня сход 44 блока 6 хранения фуищг/юиальнух записей, где они преобразуются в сообщения, которые паре- даются с выхода 49 блока 6 на вход 50 блока 7 хранения редуцируемых п жетов. Это со- оощение необходимо для спуска ожидаю- щмх пакетов, О писан;- г я саязь позволяет организовать адаптивные режимы функционирования, в которых пг. редукции па- опоодс . результатами текущих вычислений,

Результаты обработч данных с выхода 23 операционного устройства 2 через блок 1 выходного интерфейса поступают ка внешнюю мзгистсаль 13 и тем самым могут быть- гшпедены иэ смстомь. Операции обмена с в - 91 1Н8й средой, .лпамые пополняемыми пакета м, осуществляют также чэрез г)ход 20 и ):од 41 блока 3 хранения струкчеоеа блоки 12 и 1. При занесении в блок 3 новых Moccwuos данных vix имена заносятся п бло 9 храпения имен данных, з при счи- тыйании с уничтожением соответствующие оглен в блок ; 9 уничтожаются, Процесс обработки завершается, когда в блоках 7 и 8 исчерпываются все редуцируемые пакеты, з п илохе 10 вот готовые ксполняемые-пакеты; Возобновление процесса обработки по тем же програг лмзк требует загрузки новых дан- и блок 3 i нового начкпьного пакета в олох 7,

Систегла потоковой обрэоотки инфор;,-;ЗЦИ -: С ИНТЗрПреТаЦЙОЙ фу -;;СЦ ЛОНЗЛЬНЫХ ; :;;ЫКОВ. СОДбОЖаЩПЯ ЁЛС1К ВЫХОДНОГО ИНТ8рфг;(;1с::;. апорсЩ-гонков усгр.оЯстсо, блок хрз- V:f .t ji-A C- iiiyixryp данных, ш;ок хранения П.;ог|:., ш; о охранения родуциоуемых пз- кетов, блок входного интерфейса л ЭВМ зв- груз ш, причем вход и выход ЭВМ загрузки чорез изп«стоаль подкл. очемы к

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

0 хранения редуцируемых пакетов, выход которого соединен с входом начального пакета редукции пакетов, выход готовности блока хранения программ подключен к одноименному входу блока хранения редуци5 руемых пакетов, выходы готового пакета и имени первого аргумента блока хранения исполняемых пакетов соединены с одноименными входами блоков обработки пакетов и хранения имен данных

0 соответственно, выходы нового имени и готовности аргумента блока хранения имен данных подключены к одноименным входам блока хранения исполняемых пакетов соответственно, выход блока хранения подпрог5 рамм элементарных функций соединен с входом подпрограммы блока обработки пакетов, выходы кода имени элементарных функций, управления и чтения которого подключены к одноименным входам блока хра0 нения подпрограмм и элементарных функций, операционного устройства и блока хранения структур данных соответственно, выходы имени блока данных и данных для внешней магистрали блока хранения

5 структур данных соединены с одноименными входами блока хранения имен данных и блока выходного интерфейса.

Изобретение относится к цифровой вычислительной технике. Целью изобретения является повышение быстродействия и расширение функциональных возможностей системы. Система содержит операционное устройство, блоки памяти для хранения структур данных, программ и пакетов, блок входного и блок выходного интерфейсов, внешнюю магистраль и ЭВМ загрузки, блок редукции пакетов, блок обработки пакетов, блоки для хранения подпрограмм функциональных форм, исполняемых пакетов, имен данных и элементарных функций. Система обеспечивает смещение процессов формирования графов и его исполнения, которое может быть также распараллелено на различных уровнях за счет нескольких блоков памяти различного функционального назначения. Система обеспечивает подключение дополнительных блоков обработки и хранения информации, в том числе специализированных, например векторных, матричных операционных устройств и т.д. 1 ил. fe