Система потоковой обработки информации с интерпретацией функциональных языков
Иллюстрации
Показать всеРеферат
Изобретение относится к цифровой вычислительной технике. Целью изобретения является повышение быстродействия и расширение функциональных возможностей системы. Система содержит операционное устройство, блоки памяти для хранения структур данных, программ и пакетов, блок входного и блок выходного интерфейсов, внешнюю магистраль и ЭВМ загрузки, блок редукции пакетов, блок обработки пакетов, блоки для хранения подпрограмм функциональных форм, исполняемых пакетов, имен данных и элементарных функций. Система обеспечивает смещение процессов формирования графов и его исполнения, которое может быть также распараллелено на различных уровнях за счет нескольких блоков памяти различного функционального назначения . Система обеспечивает подключение дополнительных блоков обработки и хранения информации, в том числе специализированных , например векторных, матричных операционных устройств и т.д. 1 ил. fe
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (я)5 G 06 F 15/16
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
flO ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4726392/24 (22) 29.06.89 (46) 07,12.91. Бюл. (Ф 45 (71) Институт кибернетики им. В.M.Ãëóøêîва (72) А.В.Пала гин, Ю.С.Яковлев, А.В. Махиборода, В.А.Карпович, Г.П.Макаров и В.К.Сергеев (53) б81.325(088.8) (56) Vasоп P. Sriпе. Аn atchltectural
compaslson of data slaw systems //
Computer, 1986, ч. 19, N 3, р.68 — 87. (54) СИСТЕМА ПОТОКОВОЙ ОБРАБОТКИ
ИНФОРМАЦИИ. С ИНТЕРПРЕТАЦИЕЙ
ФУНКЦИОНАЛЬНЫХ ЯЗЫКОВ (57) Изобретение относится к цифровой вычислительной технике. ЦелЬю изобретения является повышение быстродействия и расширение функциональных возможностей
Изобретение относится к вычислительной технике и может быть применено при построении ЭВМ различного назначения, в том числе и персональных ЭВМ.
Целью изобретения является повышение быстродействия и расширение функциональных возможностей системы.
На чертеже приведена схема системы.
Система содержит блок 1 выходного интерфейса, операционное устройство 2, блок
3 хранения структур данных, блок 4 хранения подпрограмм функциональных форм, блок 5 хранения подпрограмм элементарных функций, блок 6 хранения программ, ». Ы,» 1697084 А1 системы. Система содержит операционное устройство, блоки памяти для хранения структур данных, программ и пакетов, блок входного и блок выходного интерфейсов, внешнюю магистраль и ЭВМ загрузки. блок редукции пакетов, блок обработки пакетов, блоки для хранения подпрограмм функциональных форм, исполняемых пакетов, имен данных и элементарных функций, Система обеспечивает смещение процессов формирования графов и его исполнения, которое может быть также распараллелено на различных уровнях за счет нескольких блоков памяти различного функционального назначения. Система обеспечивает подключение дополнительных блоков обработки и хранения информации, в том числе специализированных, например векторных, матричных операционных устройств и т.д. 1 ил. блок 7 хранения редуцируемых пакетов, О блок 8 редукции пакетов, блок 9 хранения имен данных, блок 10 хранения исполняемых пакетов, блок 11 обработки пакетов, блок входного интерфейса 12, внешнюю ма- © гистраль 13 и ЭВМ 14 загрузки, которая своими входом 15 и выходом 16 подключена к внешней магистрали 13, с которой соединены первый выход 17 блока 1 выходного интерфейса и выход l8 блока 12 входного интерфейса, выход 19 данных блока 12 соединен с входом 20 данных блока 3 хранения структур данных, выход 21 данных которого подключен к первому информационному входу 22 операционного устройства 2, вы1697084 код 23 которого подключен к первому информационному входу 24 блока 1 выходного интерфейса, выход 25 программ блока 12 входного интерфейса, подключенный к входу программ 26 блока 6 хранения программ, выход 27 начального пакета блока 12, соединенный с входом 28 начального пакета блока 7 хранения редуцируемых пВКВТОВ, выход 29 подпрограмм функциональных форм блока 12, подключенный к одноименному входу 30 блока 4 хранения подпрограмм функциональных форм, выход 31 подпрограмм элементарных функций блока
12, подключенный к одноименному входу 32 блока 5 хранения элементарных функций, вход ЗЗ кода имени элементарных функции которого соединен с одноименным выходом
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 редукции и IK8ToB, вход 63 фрагмента записи которого подключен к оцноименному выходу 64 блока 6 хранения программ, вход 65 запроса программ которого соединен с выходом 66 запроса программ блока 8 редукции пакетов, выход 67 запроса подпрогэаммы функциональных
10 ные языки состоят из следующих основных компонент: набора элементарных функций, 15 набора функциональных форм, позволяю20
40 форм которого подключен к одноименному входу 68 блока 4 хранения подпрограмм функциональных форм, выход 69 которого соединен с входом 70 подпрограммы блока
8 редукции пакетов, выход 71 готового пакета блока 10 хранения исполняемых пакетов, соединенный с одноименным входом 72 блока 11 обработки пакетов.
Система ориентирована на обработку данных в режиме интерпретации записи алгоритмов обработки на функциональных языках, Интерпретируемые функциональщих конструировать сложные функции из элементарных, набора функциональных определений. представляющего собой библиотеку функций, сконструированных из элементарных средствами функциональных форм.
Данные в системе представляются словами фиксированной разрядности, состоящими из двух полей: поля тегов и поля информации (например, поле тегов 16 разрядов и поле информации 32 разряда).
Данные организуются в массивы, имеющие определенную структуру. Элементарные функции onределяются над массивами, Доступ к массивам осуществляется по именам.
Управляющая информация представляется в виде пакетбв. Пакет представляет собой запись, состоящую из следующих полей: имя первого аргумента, имя второго аргумента, имя функции, имя результата, поле управляющих флагов,(например, именные поля по 16 разрядов и поле флагов 8 разрядов — всего 72 разряда).
Работа системы основана на аппаратной интерпретации функциональных языков, порождении графа программы в режиме редуцирования функциональных записей и исполнении графа программы в режиме управления потоком данных. При этом все указанные процедуры совмещены во времени и согласованы по скорости выполнения.
Базовые операции функционального языка и базовые структуры данных реализованы микропрограммно в соответствующих устройствах системы и в широком диапазоне представления; от элементарных арифметических операций над скалярами до крупных функциональных операторов над блоками данных, имеющих структуры векторов, матриц, списков и т.п, Архитектура системы построена так, что она позволяет осуществлять одновременное порождение процесса и его выполнение в виде потока
1697084 пакетов с текущим уничтожением обработанных и ненужных пакетов. При этом пакеты преимущественно инициируют перемещения крупных блоков данных и выполнение крупных функциональных операций над ними.
Принятая организация процесса соответствует структуре функционального языка и создает условия для его эффективной реализации, Инициализация системы состоит из трех фаэ: загрузки интерпретатора, загрузки программы и данных, занесения начального пакета.
Загрузку интерпретатора системы осуществляют с помощью ЭВМ загрузки через внешнюю магистраль 13 путем записи программы выполнения элементарных функций и подпрограмм реализации порождающих редукций, соответствующих функциональным формам. Загрузку осуществляют в блоки 4 и 5 по входам 30 и 32 соответственно через блок 12 входного интерфейса. В блок
4 также загружают библиотеку используемых функций.
По сигналу "Сброс", проходящему с внешней магистрали 13 (цепи сброса не изображены), память блоков 3, 6 —,11 и регистры операционного устройства 2 обнуляются, В блок 6 хранения программ по входу 26 по внешней магистрали 13 через блок 12 входного интерфейса в режиме пословной передачи информации поступает программа (или набор программ), представляющая собой последовательность символов функционального языка. При этом ЭВМ 14 загрузки предварительно осуществляют компиляцию записи, размечая ее на блоки и присваивая метки, необходимые для связывания полей редуцируемых пакетов с фрагментами и блоками функциональных записей.
B блок 3 хранения структур данных по входу 20 с внешней магистрали 13 через блок 12 входного интерфейса в режиме пословной передачи информации поступают структурированные блоки данных, представляющие собой векторы, матрицы, многомерн ые массивы, списки и т.и., обозначенные определенным именем и оформленные в виде последовательностей слов описанного формата. Одновременно с приемом и размещением данных в блоке 3 происходит выделение и передача имени блока данных с выхода 47 блока 3 на вход
48 блока 9 хранения имен данных, который запоминает имена всех данных, размещенных в блоке 3.
50 функционирования блоков 4 и 6-8 является поток исполняемых пакетов, образующих
55 граф траектории вычислительного процесса. Блок 10 хранения исполняемых пакетов, принимая пакеты из блока 8 по входу 54, определяет готовность данных, являющихся аргументами принятого пакета. С этой целью имя первого аргумента поступает с
Для инициализации процесса обработки информации в блок 7 хранения редуцируемых пакетов по входу 28 из внешней магистрали 13 через блок 12 входного интерфейса загружают начальный пакет, который имеет структуру полей, описанную выше. Редуцируемые пакеты отличаются от исполняемых пакетов тем, что в их именных полях содержатся ссылки на функциональные формы и функциональные записи. Для распознавания характера ссылок служат соответствующие флаги.
Блок 7 хранения редуцируемых пакетов принимает также по своему входу 50 с выхода 49 блока 6 сообщения, которые используются для определения готовности пакетов к выполнению операции редукции. Готовый к редуцированию начальный пакет с выхода
61 блока 7 поступает по входу 62 в блок 8 редукции пакетов. Блок 8 расшифровывает поля пакета, в результате чего с выхода 66 блока 8 на выход 65 блока 6 поступают сигналы запроса на требуемый фрагмент записи, а с выхода 67 на вход 68 блока 4— сигналы запроса на требуемую подпрограммуфункциональной формы. Фрагмент записи с выхода 64 блока 6 и требуемая подпрограмма с выхода 69 блока 4 поступают в блок 8 редукции пакетов по соответствующим входам 63 и 70 этого блока. В результате выполнения редукции исходный пакет, занесенный в блок 7, уничтожается и заменяется одним или несколькими результирующими. При этом блок 8 определяет тип полученных результирующих пакетов.
Если пакет является редуцируемым, он может быть готовым или неготовым к редуцированию. Готовый пакет используется как исходный для выполнения следующего шйга редукции. Неготовый пакет с выхода 52 блока 8 редукции пакетов поступает на вход
51 блока 7, который переводит его в готовый пакет по приходу соответствующего сообщения на вход 50 из блока 6. Результирующий пакет считается исполняемым, если он содержит ссылки только на элементарные функции и данные, являющиеся аргументами элементарных функций. Исполняемый пакет с выхода 53 блока 8 редукции пакетов поступает по входу 54 в блок 10 хранения исполняемых пакетов, где запоминается.
Таким образом, результатом совместного выхода 5(3 блока 10 на Вход,5(".) (3лгп<3 ;.):;(33Нени5 ИМРН ЦЕ<нны) if ГВ< "- i <1< (Dif<>fqii и)" < " г0 по(лска блок 9:3 "Ip,-.,i<,-)л лет !13ïJ Jif, :::, зяп(3<3ГБBнных дан .)!1;< Б б
С Г(3уКТур дяННЫ. .<, П!ЗИ Ня/ "i" f<)b 3=11! f::iif. !<)H! I()
Го ИМЕНИ В бЛСКЕ 91!а аГО I ЫХ(3,г:-. 00 (3
:Г<ОЛНВЕтСБ ДЛЛ ОПРЕ((;)Ле,- ИЛ ГС С.. -::,Ст(/1 .с(<. рого аргумента. /3ялее блок "j 0<»fii.:,: - Б/-:.-<т
Е НЯЛИЗ, ГОТОВНО
J3H0CJ/ITCH В Г)118 РЕД(Г).:, гГ 1 г18 О .<,. <(<.-., гil jii,,;,<
f P f/f x 0 P 3 Да и н ь! х, K 0 f 0 ") ", s! т (1 к): «:. LI 0 B J< 61 !LJ 8;-,;-:
Б д)3) ГОЙ Внут )3 !! не,! Г(я "r)! I! <(Г <)K< I 1 (1, ПрИ 00(T)iПЛ!-".!J! !.i но <4 ) ;:,,. -1(:(i, (??>
ВыхОДе! 5!/ б)л оке, 9 Б блрк 0 Р<)8 <и )(Гг<-BB-.;:
СТВУ)ОЩИИ ВХОД Э Р. Г(36 (, I<3!1<",<. l/JI < Г г.(3<33,;,.
Н И 8 НОВОГО ИМЕНИ С И /л Г I 3 F ii (Пакетов1 0)кидак3ЦЗУ<): Г)рл;<ОДР .: =-i-I b
ИХ СОВПЯДЕНИИ БЗБО/(Г(СЯ 03 Гг»8,:) .,:<3((и: флаг готовнOcT!1 аа(! -!ы) (ггс:()<1:.: !; 13.13-(::-., ! ОТО(ЗНОСТИ ДЯННЫХ 3 )3 3 .. О "< ;)i -ii 3!1!. "
ПРИХОДа Да ННH (, àíc/)Èi:i,f!)ÈJ() i C =, -.<)<. г, Л !, r и в момент выполнепил у<:лг/ви(< .-: --<3:)(!o-;--, i3cBx ярг)/ментов коHKpBTI ((i пя)<<:тя « .< (38НО<3ИТСЯ В ОчередЬ f 0 J i)<)ы;< 31)К<3. D : . Г ТГ, "
В! 18 ГIЯКБТЫ С )ЗЬ!ХОДB!, i !: K3!, " < *.; <.;1
ИСПОЛ H ß B Ì bf X Г) Я К 8Т Д Б П 0 (. T У (i 3 i -!:. i . .):<0
72 в блок 11 сбряботки:-(:« Бт:):, Блок 11 обрабо KKi ц !iBT<)l: пя")H,/мя„- .
ГОтОВый пакет из блг)1:-< 0 и ri ii!" «=,," БЛБ -"
РасшифРОВкУ 8ГО по lей =) и <3<;.".».Р"Д;) Я 1 зл -.Ип .
CTYi, ОПРЕг(8ЛЛ8МОЙ ЕГО,1ДГН j<3":".МЯ!"1<Л !:)"! ." роп рограмм; м(л), ра Гл)ого)кеннь!i Г;; „=,::,—:,:.:
5il0ке, Блок . 1 В<=. pягят .! 1 .<6:. i ".!Лг - ..!! i-i! )"... <и
ЯРГУМЕНТОБ.,,OAДОВС":, /)ЯЕЬ)ь:Р .<<г .;П) —,, НИЯ KOTO13bf6 BIÜÎ О/ ii ): 1()г "i <" 3 " j э <
40 (3/IDK3 3 х<3яне(-ия стр, кт"/р i)ü÷,i;Ix, ко-„",ц Ы Й ОСУ (ц л г )-,J) i) 81.г 0 (i f i (СМВ0В И ИХ П6<38СЫЛК :. Б .-.Д".i)4,!,3 (,<:)Г
Bbfx0J(22 0()Pp3!)MOI-! I-) О Г< < < .. Т<30Й. =)3 ..: / НОВГ36МВН НО КОД ИМЕНИ Е/)<Я :16 -1: Я 3 -Н:)(:;(1" . 1 К.
Ции(. Выхода 34 блока f(: ("ц ця,", ):,х ) 1
33 B ол(3К 5 х(33HCI-ff г:,.(I(I pii ()я(,,)Ь< .) /; < тарных функ((и(л. Бл(K )3 (i;",:. <. ): .с е,::, 0
Зап(3013)8н нОЙ ПОДп Рг)ГiI
РаММУ В ПОСЛЕДОВЯтЕПЬН<.;Ст -, /nг,;:БЛВК. <Д ::
СЛОВ И СИГНЯЛОБ. ПB,!::,<(i,,
Онное устрой тво 2 с выходя 3, блока 11 HB
Бхо <3,<Г) i3/) (Of<é,!, ПО ЗЯБРОГБBнии Обг)аботки де!Н((ых Б ОГ!еое(((!1<)ь(ном )/(т сйстБР с Быхо33 ) (ЗЛО(.) 2 )!я ВХОД 24 (;кя < г Ог туг)я!От !
36ЗУ/1 !.. <Я;;", .:()Ц РОБО)1<Д<38М „)6 С::ГН„)ЛОМ з е « и;.-,:,;:I T 3 K j" е ". е .)ул ь- я. 3;.,i ц с л н 6 н и sl 0 ц 8(. Я <) < Й. / (/1 Ят 0 "Oi:,-j J 0 K, j di О Р М и 0 У Е- 11 г, 8 Р Е/):-!Вг Г „(1!-(ходя 37 !(я RxÃ:,ÃI 38 Оцеряц()он -f(300 .:Г(30.)c Бе- 2 ..)Π—:Бе<СЗБ;if!3LL!ие команды, С
i, i, < i!;;;;. 4;=), ;:;,()K;-. . j П;;:<
f ;(<;,;.:::>
;i;. A, ке!. -ii" : Нь)м B n3! ете езу/)ь я j û Об1 l I j D Г К и (1 Я Н Н Ь! . : Б С): i 8 0 Я И 3 г!! ) O М У < Т О О Й С Т Б 6 . .;.1(.::.. т быт)= т<:.<3«<3 пеL3е8<дань< с Бь:;<ода 23
:,-(г,гц ij."" -,) i;" г)г, з б 10i. 1 „1 r . 3л 4 3 л1г;< 3 ." ) :" "нi,!,i <() !. <(3,"йнальн ..! Яя:()исBЙ Где Они
:-!1)ес брязукп- ..-: .:. со<3б(),<-:ни.:;. которь е пере, 1 >10! Св (Б = 3;<)ЛB 4<(<б/!(3к::) 3 1<<3 ("ход 0 блока ,, Г;яь(()1-1<) 0."i. :, :МD ij )Б « <3,<С (Н <3Х<И (! ЭIO
< ip(;-, H,; DB ) rf.. - } Бяцти Б н) 8 06,< yмь!
<10 .. -".«с j» ".:i. 30i-< Пг О:I;= г Г)г <" - <, <, IB
;) ./ )Ь) Я Г<1 00f i3()ot . >
1 1; ° (- г; ..-, < <,;О ° I I, ")I:.,ð"ã-г-i i-)Й(TB „. ., ц< ; гз с (<01 л . <..: . i f) f г) ;„< ц-.-1< Я)(IT)rn; DC-ii,iг<, (г)т на Б,:-(Е()<;-i„ ii <ИЯГИС i 1- )Л<-; !; 1 i „,I, i ;СЯМЬ(<, С)Г Т :ЫТЬ
/ ..)<,«3 -<,<- Ii.;,-: )<(-:.- ") 1: }i)0;-BL(!/<И Ц 3(. 6:<Р Г
))1<" Ц)1 Р/ I Ц< Ггцй i 1ГЗЯ< Л) - Л .!6 . i ГЛ - Яе
r< г:, 3/, I.i riI r ii ), < бГOã :. 3 с !л)i (O iK:",, Д дан нь .. <;; )дин,; —, 1! i,—,,"„!()Г<ЛС ) ДЯДЬ 0 f ;
"./:.<-,Р = <3!)Г i,; I .) iri j.,1г<И ". «. -1" г Н(i "j б
, ", :X!;)3C И iп!= Дя -)(!Ь "". !)Х ИМЕНЯ ЗЯНОСВТСБ ,! БЕ)НИV< C )/(- ИЧ3 (<)К6НИЕ" ) СООТВ8ТСТЗУ, О< (Ие, I
;,;гз I B <3>
i;;" !6< П!.«)-.K)T;-,::;,ГГ. (36Д)/(! ИР)/ЕМ ЫГ- ЦЯ!<8;-Ы, Я
<,1ц; . < (,<:,,-. гг -Б 1 г <:(ц i(< Í ã;,: (...)К(с Пp!< ТЫ;
-)3<1,.,1(г,B/I()f- ие Il,30
Г<,ir,,",т!,13 /)гп <)КОБОЙ обдядо ц<и инфор3
:;: Я< i)1! 1 ; n Ili Br n 08 i а (< ". ;Й
1 j3 . i""-" П("1 <" rX/" .< и,:-i - (Oii 1< "/1 ЗЯГО /ЗК() 1697084
10 первому информационному выходу блока выходного интерфейса и к информационному входу блока входного интерфейса соответственно, выход данных, выход программ и выход начального пакета блока входного интерфейса соединены с одноименными входами блока хранения структур данных, блока хранения программ и блока хранения редуцируемых пакетов соответственно, выход данных блока хранения структур данных, подключен к первому информационному входу операционного устройства, выход которого соединен с первым входом результата блока выходного интерфейса, о тл и ч а ю ща я с я тем, что, с целью повышения быстродействия и расширения функциональных возможностей системы, в нее введены блок редукции пакетов, блок хранения подпрограмм функциональных форм, блок хранения исполняемых пакетов, блок хранения имен данных, блок хранения элементарных функций и блок обработки пакетов, причем выходы подпрограмм функциональных форм и элементарных функций блока входного интерфейса подключены к одноименным входам блоков хранения подпрограмм функциональных форм и элементарных функций соответственно, второй и третий информационные выходы блока выходного интерфейса соединены с входами результата блоков хранения программ и структур данных соответственно, выходы запроса программ и подпрограмм функциональных форм блока редукции пакетов подключены к одноименным входам блоков хранения программ и подпрограмм функциональных форм соответственно, выход подпрограммы блока хранения подпрограмм функциональных форм и выход фрагмента записи блока хранения программ соединены с одноименны5 ми входами блока редукции пакетов, выход исполняемого пакета которого подключен к одноименному входу блока хранения исполняемых пакетов, а выход неготового пакета подключен к одноименному входу блока
10 хранения редуцируемых пакетов, выход которого соединен с входом начального пакета редукции пакетов, выход готовности блока хранения программ подключен к одноименному входу блока хранения редуци15 руемых пакетов, выходы готового пакета и имени первого аргумента блока хранения исполняемых пакетов соединены с одноименными входами блоков Обработки пакетов и хранения имен данных соответственно, выходы нового имени и готовности аргумента блока хранения имен данных подключены к одноименным входам блока хранения исполняемых пакетов соответственно, выход блока хранения подпрограмм элементарных функций соединен с входом подпрограммы блока обработки пакетов, выходы кода имени элементарных функций, управления и чтения которого подключены к одноименным входам блока хранения подпрограмм и элементарных функций, операционного устройства и блока хранения структур данных соответственно, выходы имени блока данных и данных для внешней магистрали блока хранения структур данных соединены с одноименными входами блока хранения имен данных и блока выходного интерфейса.
1697084
Составитель В,Сычев
Редактор И,Шмакова Техред M,Моргентал Корректор Т.Малец
Заказ 4307 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
1 3035, Москва, Ж-35, Раушская наб., 4/5
Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина, 101