Устройство для параллельного формирования адресов

 

Изобретение относится к вычислительной технике и может быть использовано в параллельных вычислительных систе.мах с общим управлением и с основной памятью. f4/ff фиг.1 состоящей из нескольких независимо адресуемых блоков. Целью изобретения является повышение быстродействия. Устройство свдержит группу регистров 1 адреса, коммутатор 3 адреса, группу регистров 4 шага индекса , коммутатор 5 индекса, сумматор 6, блок 7 запоминания индексов, сумматоры 8, группу схем 9 сравнения, блоки 10 групп элементов И, регистр 1 1 максимального индекса , элемент ИЛИ 12, триггер 13, входы и выходы устройства. Устройство позволяет одновременно формировать ,V адресов элементов обрабатываемого вектора, что в N раз повышает быстродействие по сравнению с применением последовательно работающего узла вычисления индексов. 2 з.п.ф-,1ы. 3 и,-1. со 00 00 со оо

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„„Я0„„1337898 (51) 4 G 06 F 9 36

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ г,г, А гг (гг

25 и фи 1

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3844840/24-24 (22) 16.01.85 (46) 15.09.87. Бюл. № 34 (72) В. В. Есипов, Н. Н. Захаревич, Г. Г. Калиш и А. А. Сорокин (53) 681.32 (088.8) (56) Авторское свидетельство СССР ,% 1062703, кл. G 06 F 9/36, 1983.

Авторское свидетельство СССР № 826350, кл. G 06 F 9/36, 1981. (54) УСТРОЙ СТВО Д.1Я ПА РАЛ Л E.1 ЬНОГО ФОРМИРОВАНИЯ АДРЕСОВ (57) Изобретение относится к вычислительной технике и может быть использовано в параллельных вычислительных системах с общим управлением и с основной памятью, состоящей из нескольких независимо адресуемых блоков. Целью изобретения является повышение быстродействия. Устройство содержит группу регистров 1 адреса, коммутатор 3 адреса, группу регистров 4 шага индекса, коммутатор 5 индекса, сумматор 6, блок 7 запоминания индексов, сумматоры 8, группу схем 9 сравнения, блоки 10 групп элемен-,îâ И, регистр 1! максимального индекса, элемент ИЛИ 12, триггер 13, входы и выходы устройства. Устройство позволяет одновременно формировать N адресов элементов обрабатываемого вектора, что в А раз повышает быстродействие по сравнению с применением последовательно работаюшего узла вычисления индексов. 2 з.п.ф-лы.

3 ил.

И300, 1(Т ilk!« ОТНОС ИТС и к H hl.! k Ñ. I. I "! Х! h! 0-1

T(. ни кс и мож T бы гь испол ь!)(> Hell i0 h !)c! . () ci. 1, )С Л 1>! 1 Ы Х 131>! Ч И С.l И 1 С,1 Ь Н Ь1. > i И С" С М c! . ;

I ll k I .>i (11 j! 3 13, I l l i! (i(t I (0 <. l 0 H i: 0, i И;! (! и: I (., СОСТ05!)ЦСИ И3 НССКО, l i>! H Х II(3313! С I l 10 !)д <)«

С > С ЫХ Й«10К013.

1(ег!ь изобретения 11<)HE>lill(ll!(Й

Д(ИСТВИ51.

На фи Г. H:!Oáîû)к(<13 ((), I: К1!И О и с>, )ьН 3 я СХ(:Vl 3 ус рой«ТE3ci; Н;! (() И Г. 2 ЙЛО К

Запоминания инд(. к«OH; !Iil фи > — б IOK групп э Iex!BIIT0H И.

) CTP0ktCTB0 C0;J cP)K k! l C f)>, l! ll, Р<и I .< ГР< IH аДРЕСа, ГРУППУ 2 ЬЧ ОДОВ НЫЧЫ," ЬИ(ГО cl,jP«С .:, УСТРОЙ«!Ва, КОММУтыПГОР ) ЫДРЕСc!, I j) Пи, Р( гистров (и!аг3 и:.1,(ексы, ко<>!х)3 гil10(i 5 и!

Д(КС!1, С> М М ВТОР (!, O, I() и» rifi!),1!! EI 3 I i)I 51 И

ДСKCÎB, Сссl(t (131 OP hl <(, 1 !) (!;I> «> ЕХ!:) Cj!-:; i;

НСНИ Я, б, 10K!i 0 Гp(llll -)л(Х!(I 1"HH И, р!

ГИСТР 1 Х1ЫКСИМс),1!И!ОГО Hil,l(.1,.;1 -).1(МС!;<1

И, IN (2, тригг f) !. ), ы рсс:!ЫЙ (- (. Выборки «)

1)ХОДЫ Й, 1 ОКс< Зси10>(! If 1!3111!Я И НДСКС О В,:3Х<:,; L) !

)ЫООР3 ГР >>ll п Ы 3: ;)(СОВ > С 1 j! 0!t!."! I! ci. Р(! . И >

В и<ХОДОВ 110«I H il H, ССK< с) О I 0Krl: 3110М И НЫ El k! H

H 1! СС К (0 В, I () > Ï П (! ) k! ) I (i<) 0 j)!>l cl J . i 0! i I!; >I ) < Х 0дов блоков (О, группу (9 вы..одOB поля ииирып)сиий адреса блîK3 3;3!,Ox!!lf!àп!!я

13 ХОД 2() М !К«ИМ с), !.ИО, ОИ; С1.li 101 (; .)Ск 3 ХС) РОЙ(ГI Ва, 13XO;Ih: ()33 )(. И!С .;5

3НЫ Кс) 0KÎI I Irl I I ИЯ riДj) C>«сl! I 3 11 ><. ГP 5 ii«! Hil, !)

II(, 2 ) !)ХОДОВ И!с .I а ИЗ",."1 СИНЯ;,I I !(«r! С(Р«И(L:!c!, 13 XO j 2- 1 131!()<) f) ic. 1 с)Д!), (;!, . " f)< !Й(":

l3i1, HX01 20 lih;00P!(li i!IcIl;i 11! - i(I::151 ! !с 1, >, ((i i!<)И 133, Il)(I: I(,; (! <<И )! >! ::., <>И, .!h1X() j0I3 I!!0K0f! ((), "Р > ! !,, !! r! <<) r и!.:!х 27 и с 1 арlllH>, 2<(pы:.! ()H:3 Ij! (< I f)ОЙ<в! Вcl. (j, !0 К 33 НОМИ:13111>!I HH L(КС!!<3 < 0Д(РЖИ ..j)J I P > III L!,!OKOH,) И 1 151. !1 ((c! 13 51 P 111 I! i!,i 51!!!

Ж li 1, (Г:1 (!! 1 )«1((I С!:"! <) 3!

У«1 PO>t(Ï30 Рc>()0! Ы«1 «СДХ.Г)(,СИХ! 0<" <)3.3(.

С)< !f0!3!! с! я а,рссуС !и 35. i! c! .15 Т Ь Б!.I ci » С

1 С,IHIIOI! СИ«т(МЦ,:i Кото IO!I . " ii!r! ".;!. ;. С! . и

Ij Ir !

Ii)I! >I « I!(ll>(. « <) 0 JI « i-!3;:., « 0 С,Ч! H !

j(X!0<. ii(X!0 (),!i)K0H. >:!«!0ll I! Нсд:! !11(i »

;)ДР((. Ill i H!! ).Сипак:)<30 i 0 1:::,и

:,, и !,Lp««)li!(!KH Основной )амяти обра.,«51 öc((15!. ((тывляк:IH!3(tè: номером блÎ1.(!, >1, И>, I I! I fr !|с).! j)!t.jh: i0, I HO I 0 3дрс Сс3 ) И

i! j) ((!» 5 ° I Ii I: и 6.1!j "ГаPI!1!!с РЗL!PßИЯ il0. <1<) (5 .I.J 0 . ci ! <>(.СHO«! i! i rl(>l (и !) Ы НЕ пи(> с), Гр(C((>М ЫХ !

ill!llhIx ь (!(. HO!3liOk! НJMЯти В BHd« ОДно >! С <) I I! ) i 0 М Ы С С И В а (В С К Т (! р с) ),: 1 р И Ч С. М СОСЕДНИЕ, I(»>1 С НТHI :3«К I OP II . МСIОТ и IT!È 1 3 Юп><ИС СЯ НЫ с. (Jt!!f3 ljv d,jPñcñl, ы lid÷û;! ьны Й Зле (tel!ò H(с:Г 0 I r! H3XO, i li! C51 в I С«I(!ВОМ б, I OK« ОСНОВНОИ

;,:<..яти. При ирпнягОМ формате адреса эт0

Оып; !ыс I, !10 )ер!)ь!«Р элементов векторы .РсlНЯ <ге51 13 Я i(. РКЫХ С 0;kit l!3i(OHhl(1 3;1РЕСО v\

(il<) H! 10k >1 > . 5-; 1 И С:IOC 1Ñ,LOI! i!T«i и<3(:

БОЗРЫ«Х) II К)lil И (i И С Il а ГО (! ОТ () ДО > ) НО(1 . t) с! 111 (\«13 L! H I! >1 И Р с!.! f) Я„ ñ! (I И 3.1()Е(3 . ., (i() Ill Hc 5;, (> (i (. i i С!3 1) Ы " .И 0«I .:! i Ы Н) . < 5. H H !(H

С rl f)Ñ«< " I .!. L(0ill li (!

1, ., с! >, 1 i . .3 ! I i " И I, ! (. и 1 I .

Ni) )) «,! (). I<» . i:

I, l 3(t(,! БС К. 0

> < !. Lrl(! i )0; f)r! М >1!1 ! !l () Ы« I:O. I с! с) "i

f!()-И 1„, j . (1,!1К !3()i l!!>iЪ 01 Р;3!)И— |! )(: и1>. I!l! i ir, . .НИ)И(К.;;c! I il(< " ll . Pcl k! ILI>l !

>;! С; !!c,(! !; 3!Oj)< !(Ili И > и . < >, ), !, ;. (!I <) ri, !i « (и <) X « l) .:l l! :!<)I3 . !

l : « ci I iI h!«H I () 1(с ., с! I i,)Ь. 1! I j) Ы i(Т (»! Hl( ;:-.>> < Г;<РИ:!1< 3,>ЯДЫ Со l!Ih ci IP< (OH, 5(!(!iir<101 . ;. !°r, I .!. I HI« i Pи Х i, ),jf (Ñil, (Х .)>С !

I cJ 0p > rI, p(«: .. I3(ri>;l 1..5; !и<00j). 0,<ИО! !.

>Ч(.<И<,:131 ii ",И.ICК<. LЫ I!0 Кс Ж . 31> !.!". (1. ili(.. .!K(1 " lici (X)

) « I I « < - . 1 li i i li I(f.!. c>. « ! ,I II I«« В, j)(<"!,5< !3 (. ! ) (I I (h K ) i(0 ;i 1 (: . r! (! p r i ) H I I, « >-! и>,{-...<„сl;; «..I;:(I С:.!. .I Oil(П!СИ Р;1(>:> ГЬ!

>.>, < !)С I И I l)(! :: I! « I". ci ! .ЗII I«li I« I il Иi !(-К< «" с:)::,0 > 31(Гав ! <) р ) 1,,СК(<, и: i ) !ЫС < 5: .3 ic cl :(Г >< i! < >С«(!

:1 (!,((11! c . (! <,:>. . Х

)<. 5

)и И. IХ . ; < ci ), <. !(сl (! К)1

,Ч и <„ 5; H . !!0! )>! >:К 11.!, !!13>! :<". < . Ы i,, (! ! !! ! (! < i ! >< ! >! ! !

1337898

При полаче сигнала разрешения на входы разрешения считывания всех блоков 29 памяти, на выходах младших )cos>P(разрядов блоков 29 с номерами с 0-го по

P — 1-й будут параллельно считаны P значе- 5 ний индексов, взятые по modP. Одновременно с этим, на выходах остальных разрядов блоков 29 памяти будут параллельно считаны Р приращений адресов ячеек основной алресуемой памяти. Указанная ситуация соответствует крайнему случаю, когда блок 7 содержит единственную группу блоков 29 памяти (/И=1, V=P). Следует учитывать, что количество сумматоров 8 и схем 9 сравнения равно количеству одновременно считываемых индексов, т. е. количеству блоков 29 памяти, на которые полается сигнал разрешения считывания в одном такте.

Структура предлагаемого устройства позволяет варьировать значения М и А, оставляя P=MN постоянным. При увеличении М и соответствующем уменьшении V количест- 20 во блоков 8 и 9 уменьшается, однако количество тактов (импульсов разрешения считывания), которое требуется для индексирования всех блоков основной памяти, растет, т. е. быстролействие устройства уменьшается, лостигая в пределе (при M=P, N=I) быстродействия последовательного формирователя адресов.

Пример параллельного формирования алресов устройством.

Предположим, что Р=16, M=N=4, шаг

30 индекса=3, регистр адреса — четырехразрядный, начальное значение адреса основной памяти=0010, верхняя граница инлекса=

=39. В первом такте (по первому сигналу разрешения считывания) на четырех инлексных группаv !7 выходов блока 7 формируются слелующие 4-х битовые колы.

Груп и ы 11 11! IV

0000 0011 01!О 1001

Олновременно, на четырех алресных группах 4О

19 выхолов блока 7 формируются колы прира гцени и алреса

0000 0000 0000 0000

Поскольку граница индекса еще не до- 45 стигнута, на выходах схем 9 сравнения сохраHHtoTcR значения потенциалов, разрешающих по входам 21 прохожление сформированных колов с информационных групп 18 входов на информационные группы 26 выходов блоков 10. В результате на группах выхо- 5О лов 27 и 28 устройства формируются слелующие адреса основной памяти

00100000 00100011 00!00110 0010!001

Обращение происходит к элементам век55 тора данных, расположенным во BTopbIx ячейках нулевого, третьего, шестого и левятого блоков основной памяти.

Во втором такте на инлексных группах выхолов 17 блока 7 формируются слелующие колы (по mod 16)

1100 1111 0010 0101, а на соответствующих адресных группах 19 выхолов — колы

0000 0000 0001 0001

Поскольку граница не достигнута, то на группах выходов 27 и 28 устройства формируются адреса

00101!00 00101!11 001!0010 00!10101, что соответствует элементам вектора данных, расположенных во вторых ячейках двеналцатого и пятнадцатого блоков основной памяти и в третьих ячейках второго и пятого блоков основной памяти.

В третьем такте параллельно формируются следующие алреса

001!1000 00111011 00111110 01000001, а в четвертом

01000100 01000111 01001010 01001101

В четвертом такте во втором блоке 9 происхолит совпадение с содержимым регистра границы. Разрешающий потенциал на вхолах групп элементов И 30 блоков 10, начиная с 3-й группы, снимается. Выдаются только адреса на 1-й и 2-й группах выходов 27 и 28 устройства, т. е. 01000! 00 и

01000111.

Олновременно сигнал сравнения через элемент ИЛИ 12 устанавливает триггер 13 и на выходе 22 устройства появляется сигнал индикации окончания работы, что привоЛит к прекращению дальнейшей полачи сигналов выбора групп на входы 16 устройства.

Таким образом, применение преллагаемого устройства позволяет олновременно формировать Л адресов элементов обрабатываемого вектора, что в М раз повышает быстродействие по сравнению с применением последовательно работающего узла вычисления индексов.

Фор.иу.lo изобрегенп.ч

1. Устройство лля параллельного формирования адресов, солержагцее группу регистров адреса, группу регистров шага инлекса, коммутатор адреса, коммутатор индекса и сумматор, причем информационный вхол

К-го регистра алреса полключен к К-мх вхолу начального адреса устройства (К=I,Н, гле

Н вЂ” количество начальных адресов), выхол

К-го регистра адреса подключен к К-му информационному вхолу коммутатора адреса, выход которого подключен к первому входу

1337898

5 первого сумматора, выхол R-и> регисгра н)ага индекса полключен к R-му информационному вхолу коммутатора инлексов, (R=1Д, гле Q -- количество шагов изменения инлексов), от гичаюи(ееся тем, «>о, с целью повышения быстродействия, в него ввелены лва блока групп элементов И, блок запоминания индексов, % сумматор (гле V ко.ги(ество параллельно формируемых адресов), группа схем сравнения, элемент ИЛИ, триггер и регистр максимального индексы, причем вход максимально лопустимого инлекса устройства полключен к информационно v1ó вхолу регистра максимального инлекса, выхол которого полключен к первым >з. î.faii схем сравнения группы, выходы которых полключены к входам элемента ИЛИ, в lxo;l которого подключен к входу установки в «1» триггера, выход которого полключеll к выхолу признака окончания алресации хстройства, управляющий вхол и выход комх(утатора индекса подключены соответсгвеifi!0 к входу выборки шага изменения инл(кса устройства и к алресному вхолу бл»ка запоминания индекса, выхо,l, комчуf3Topà алрсса полключен к первым входах) .умчаторов с второго по (% 1) -й, !-й вхол раз решения с(итывання которого полклю f I! к !

-»1Х ВХОЛ) BblOOP3 ГРХ lll!11 3Л>)ЕСОВ Х T ройства ((=!,М, глс >1) — количество I3iл поли инлекса ()лока запоминания инлсксов и выхол и-I 0 сумматора полключены к tl-M информационным вхолам соответственно и pI30I0ff Hторого блоков групп элементов И, (n= 1, V), и-ньн информационные выходы которых lio;.клк>ч(Hhl к и-м выходам соответственно м 13,1III H x и стар п(их р<1зрялО В 3лреса ус! р() Йс". 6 ва. и-й выхол схсчь> срав .)ения группы полкл(о>>он к и-му вхолу разрешения выдачи информации первоп> и BTQ :)010 блокОВ групп э,l(. ментов И, и — Й Бf>lõî1 поля инлек(а и

tl-й выхол поля прира(цеIIHH адреса блока

5:fàIIOминаfièÿ инлсксов подключены к второму

lfх0лу и-й схемы сравнения группы, и-и вь:ю;.1(оля приращения блока запоминания ин1ск rf поЛклк>чен к второму Bxoó, и-10 сх мчатора, инфор >131(1(онный вхол R-f o pe10 )истра )нага инлек;3 груп 1ы полклю(е!I к

R->f вxîäó шага изм(неiiия индекса группы хстройства

2 Устройство Ilо и. 1, Ог>гичаюи еес>г тем, гго блок запоми(.3HHB filiлексов содержит

15 .И I px fill блоков вамя.ги, причем алресные

1)холы блоков пах)яти групп подключены к 3лресно лу входу блока, входы разрешения считывания блоков памяти (-й группы полключены к !-му вхолу разрешения считывания блока, в ixo.f, чладших разря 1ов и

20 выхол старших разрядов и-го блока памяти !

- и I póffïû,fîäêëючены соответственно к

ti- хlх вы.;олх (юля индекса H tl-чу выхолх ноля:(риращения if,ið(03 групп выхо loB (),н>ка

25 3. Устройство но и. l, отличаюи(ееетг тех), i:0 блок групп >лсчентов И солержит Л

I ру:ill элсчентов Н, причем Bhfxolf>f э.(ементов И и- и груlllll i подключены к и-чу

I! нформационffox(у вь(холх î Iof(3, tTi-й инфорxf3i1H0ilii»if) вхол которого полключен к fiep30 Выч в;одам эл(х снтов И ti-й груil(lf>l блока, ) и- и вхол разрен>ения вылач и информации ()л01,3 Ilo. 1êtfк>чi(. H v (иг- — 1 ) — м вхо;13 х1 э,1ечспггов И f ) x ш: с f ги — 1) -й по ) -ную б.)ока, ni=- 1.Л 1.

Составитель М. Силин

Редактор И Касарда Техред И. Верес Корректор И Марека

Заказ 413214i Тираж 672 Подписное

ЕЗНИИГ1И Гос1дарственного комитета СССР по делам изобретений и открытий

I 13035, Москва, Ж 35, Раушская наб., д. 4 5

11роизнодственно-полиграфическое предпр«ятиe, г. Ужгород, ул 1Iроектная. 4