PL165457B1 - Uklad eliminacji zaleznosci danych przetwarzanych w komputerze PL - Google Patents

Abstract

1. Uklad eliminacji zaleznosci danych prze- twarzanych w komputerze, zwlaszcza w komputerze o architekturze pozwalajacej na szeregowe wykony- wanie sekwencji operacji skalarnych, zawierajacy jed- nostke arytmetyczno-logiczna, znamienny tym, ze zawiera rejestr rozkazów (50) z co najmniej dwiema tablicami pamieci (52, 54), co najmniej trzy rejestry uniwersalne (63), kazdy dla jednego argumentu ope- racji, uklad przelaczajacy (64), który jest dolaczony do wspólnego wyjscia rejestrów uniwersalnych (63), uklad logiczny (60) dekodowania i sterowania, które- go wejscia sa dolaczone do wyjsc rejestru rozkazów , (50), wyjscie(62) wyboru rejestru jest dolaczone do ukladu przelaczajacego (64), a wyjscie (66) wyboru funkcji dolaczone do jednostki arytmetyczno-logicz- nej (65), przy czym jednostka arytmetyczno-logiczna (65) ma trzy wejscia (A10, AI1, A12) argumentów operacji dolaczone do ukladu przelaczajacego (64) oraz ma wyjscie (A0). FIG. 8 PL

Description

Przedmiotem wynalazku jest układ eliminacji zależności danych przetwarzanych w komputerze, zwłaszcza w komputerze o architekturze pozwalającej na szeregowe wykonywanie sekwencji operacji skalarnych.

Przetwarzanie potokowe jest standardową techniką stosowaną przez konstruktorów komputerów dla polepszenia wydajności systemów komputerowych. W przetwarzaniu potokowym instrukcja jest dzielona na kilka kroków lub faz, którym przydzielany jest sprzęt zapewniający realizację funkcji odpowiadającej danej fazie. Szybkość przepływu instrukcji pteee potok zależy od szybkości wprowadzania nowych instrukcji do przetwarzania potokowego a nie od długości potoku. W idealnej strukturze potokowej, gdzie do potoku jest podawana maksymalnie jedna instrukcja na cykl, przepustowość przetwarzania potokowego, mierzona liczbą instrukcji wykonywanych w jednostce czasu, zależy tylko od czasu cyklu. Jeżeli premie się czas cyklu realizacji n-stopniowego przetwarzania potokowego jako równy m/n, gdzie m jest czasem cyklu odpowiad^ej rzelizecji nie wykorzystującej techniki przetwarzania potokowego, maksymalna możliwa poprawa uzyskiwana przez przetwarzanie potokowe wynosi n.

Przedstawione powyżej stwierdzenia wskazują, że przetwarzanie potokowe daje potencjalne n-krotne zwiększenie wydajności systemu komputerowego, kilka praktycznych ograniczeń powoduje, że rzeczywiste zwiększenie wydajności jest mniejsze niż uzyskiwane w przypadku idealnym. Ograniczenia te wynikają z istnienia zatorów przetwarzania potokowego. Jako zator przetwarzania potokowego określa się dowolny aspekt struktury przetwarzania potokowego, który przeszkadza w przesyłaniu instrukcji przez potok z maksymalną szybkością. Zatory przetwarzania potokowego mogą być spowodowane zależnościami danych, konfliktami strukturalnymi związanymi z zastosowanym sprzętem, zależnościami sterowania i innymi czynnikami.

Zatory zależności danych są często nazywane zatorami odczytu-zapisu lub blokadami zapisu-odczytu ze względu na to, że pierwsza instrukcja musi zapisać swój wynik, zanim druga instrukcja może zostać odczytana i wykorzystać ten wynik. Celem umożliwienia realizacji tego zapisu przed odczytem, wykonanie odczytu musi być zablokowane do chwili aż wystąpi zapis. Ta blokada wprowadza do wykonywania zablokowanej instrukcji cykl braku aktywności, często określany jako ugrzęźnięcie. Dlatego dodaje się jeden cykl do całkowitego czasu wykonania instrukcji ugrzęźniętej i przez to zmniejsza się przepustowość potoku. W przypadku realizacji sprzętowej, detekcja i eliminacja zatorów strukturalnych i związanych z danymi może powodować nie tylko obniżenie wydajności ze względu na niedostateczne wykorzystanie sprzętu, ale staje się także krytycznym punktem komputera. Taki sprzęt powodowałby ograniczenie osiągalnego cyklu czasowego komputera. Z tego względu zatory mogą ujemnie wpływać na dwa czynniki przyczyniające się do przepustowości potoku: liczbą instrukcji wykonywanych w cyklu i czas cyklu komputera. Istnienie zatorów wskazuje zatem, że planowanie lub porządkowanie instrukcji wchodzących do struktury potoku posiada wielkie znaczenie przy usiłowaniach osiągnięcia efektywnego wykorzystania sprzętu z przetwarzaniem potokowym.

Efektywne wykorzystanie sprzętu wpływa z kolei na polepszenie wydajności. W istocie, porządkowanie potoku jest próbą wykorzystania potoku do jego maksymalnego potencjału poprzez próbę uniknięcia zatorów. Szeregowanie może być osiągnięte statycznie, dynamicznie lub przy połączeniu obu technik. Szeregowanie statyczne jest uzyskiwane przez przyporządkowanie sekwencji instrukcji przed wykonaniem na równoważny strumień instrukcji, który będzie wykorzystywać sprzęt w sposób bardziej pełny niż poprzedni. Przykład statycznego szeregowania jest podany w tabeli 1 i tabeli 2, w której uniknięto blokady pomiędzy dwoma instrukcjami Load.

165 457

Tabela 1

XI

X2

ADD R4, R2 LOAD R1, (Y) LOAD R1, (X[R1]) ADDR3 LOMP R1, R4 SUB R1, R2 COMPR1 X3 X4 ; dowolna instrukcja ; dowolna instrukcja ; R4 = R4 + R2 ; ładuj Rl z komórki Y pamięci ; ładuj R 1 z komórki X pamięci funkcji R1 ,R1; R3 = R3 + R1 ; ładuj uzupełnienie binarne (R4) do R1 ; R1 = R1 - R2 , R3; porównaj R1 z R3 ; dowolna instrukcja złożona ; dowolna instrukcja złożona

Tabela 2

XI ; dowolna instrukcja

X2 ; dowolna instrukcja

LOAD R1, (Y) ; ładuj R1 z komórki Y pamięci

ADD R4, R2 ; R4 = R4 + R2

LOAD R1, (X[R1]) ; ładuj R1 z komórki X pamięci funkcji R1

ADD R3, R1 ;R3 = R3 + R1

LOMP R1, R4 ; ładuj uzupełnienie binarne (R4) do R1

SUB R1, R2 ;R1 = R1 - R2

COMP Rl, R3 ; porównaj R1 = R3

X3 ; dowolna instrukcja złożona

X4 ; dowolna instrukcja złożona

Jakkolwiek techniki szeregowania mogą wyeliminować pewne zatory, powodując polepszenie wydajności, nie wszystkie zatory mogą być usunięte. Dla zależności danych, które nie mogą być wyeliminowane przez szeregowanie, zostały zaproponowane pewne rozwiązania. W proponowanych rozwiązaniach wykonuje się wielokrotne operacje równolegle. Według jednego z nich strumień instrukcji jest analizowany sprzętowo i zgrupowany w instrukcji złożonej do wyprowadzenia jako pojedyncza jednostka. To podejście różni się od maszyny superskalarnej, w której wiele instrukcji jest zgrupowanych ściśle na zasadzie FIFO (pierwszy na wejściu pierwszy na wyjściu) w celu jednoczesnego wyprowadzenia. Przy założeniu, że sprzęt odpowiedni do jednoczesnego wyprowadzania dwu instrukcji, maszyna o złożonych instrukcjach zestawiałaby w pary sekwencje instrukcji z tabeli 2 następująco: (-X1) (X2 LOAD) (ADD LOAD) (ADD LCMP) (SUB COMP) (X3, X4), przez co unika się zależności danych pomiędzy drugą instrukcją LOAD a drugą instrukcją ADD. Porównywalna maszyna superskalarna jednakże tworzyłaby następujące pary instrukcji: (X1X2), (LOAD, ADD) (LOAD,ADD), (LCMP SUB) (COMP X3) (X4-), stwarzając ryzyko zależności danych LOAD-ADD.

Drugie rozwiązanie dla pokonania zależności danych zostało opisane w czasopiśmie Computer Architecture News z marca 1988 r. w artykule W.A. Wulfa pt. Architektura komputera WN. W architekturze tego komputera proponuje się stworzenie zbioru instrukcji, który zawiera więcej niż jedną operację w pojedynczej instrukcji, dopuszczenie blokad rejestru w tej instrukcji oraz połączenie kaskadowe dwu jednostek arytmetyczno-logicznych, jak pokazano na fig. 1, celem eliminacji blokady w pojedynczej instrukcji. W tej propozycji nowe instrukcje muszą być stworzone dla wszystkich par sekwencji instrukcji, których blokady mają być wyeliminowane. Wynikiem tego jest albo niedopuszczalna liczba kodów operacji zdefiniowanych dla nowego zestawu instrukcji albo zostaje nałożone ograniczenie określone przez liczbę dostępnych kodów operacji na liczbę sekwencji operacji, których blokady mają być wyeliminowane. Ponadto ten schemat nie musi być kodem wynikowym zgodnym z wcześniej165 457 szymi zastosowaniami architektury komputera. Inne takie schematy posiadają wymagania dwu jednostek arytmetyczno-logicznych, których połączenie łańcuchowe może spowodować wykonanie instrukcji wielokrotnej operacji wymagającej prawie podwójnego czasu wykonania pojedynczej instrukcji. Taki wzrost czasu wykonania odbijałby się we wzroście czasu cyklu komputera i w sposób nieuzasadniony obciążał wszystkie wykonania instrukcji.

W przypadku, gdy dany komputer posiada architekturę przystosowaną do sekwencyjnego wydawania i wykonywania danego zestawu instrukcji, byłoby korzystne zrównoleglenie wydawania i wykonywania instrukcji. Równoległe wydawanie i wykonywanie intrukcji zwiększałoby przepustowość komputera. Dalsze korzyści z takiej równoległości powinny być zmaksymalizowane przez 'zminimalizowanie zwłoki wykonania instrukcji, wynikajacej z zatorów zależności danych w potoku instrukcji. Z tego względu zastosowanie równoległości powinno dać zmniejszenie takiej zwłoki przez eliminację blokad spowodowanych tymi zatorami. Korzyści te powinny być jednakże uzyskane bez konieczności opłacania ich kosztami wynikającymi ze zmian, architektury danego komputera, tworzenia nowego zbioru instrukcji celem utworzenia wszystkich możliwych par instrukcji i ich kombinacji, zawierających blokad oraz dodawanie sporej ilości sprzętu. Następnie adaptacja taka powinna posiadać niewielki lub żaden wpływ na czas cyklu komputera.

Przykładem istniejącej architektury komputera jest sekwencyjna maszyna skalarna, wytwarzana przez International Business Corporation. Może nim być komputer zawierający architekturę System/370, architekturę rozszerzoną System/370 (370-Xa) i architekturę systemów przedsiębiorstwa System/370 (370-ESA). Ich opisy zostały przedstawione w Zasadach działania Systemu/370 IBM, publikacja nr GA22-7000-10 z 1987 r., i w Zasadach Działania Architektury Systemów Przedsiębiorstwa/370, publikacja nr SA22-7200-0 z 1988 r.

Istotą układu eliminacji zależności danych przetwarzanych w komputerze, zwłaszcza według wynalazku w komputerze o architekturze pozwalającej na szeregowe wykonywanie sekwencji operacji skalarnych, zawierającego jednostkę arytmetyczno-logiczną, jest to, że zawiera rejestr rozkazów z co najmniej dwiema tabelami pamięci, co najmniej trzy rejestry uniwersalne, każdy dla jednego argumentu operacji, układ przełączający, który jest dołączony do wspólnego wyjścia rejestrów uniwersalnych, układ logiczny dekodowania i sterowania, którego wejścia są dołączone do wyjść rejestru rozkazów, wyjście wyboru rejestru jest dołączone do układu przełączającego, a wyjście wyboru funkcji jest dołączone do jednostki arytmetycznologicznej, przy czym jednostka arytmetyczno-logiczna ma trzy wejścia argumentów operacji dołączone do układu przełączającego oraz ma wyjście. Następnie zgodnie z wynalazkiem jednostka arytmetyczno-logiczna zawiera sumator, którego trzy wejścia argumentu operacji są dołączone do wejść argumentów operacji tej jednostki a jedno wyjście wyniku jest dołączone do wyjścia tej jednostki.

Korzystne jest, gdy zgodnie z wynalazkiem sumator zawiera sumator ochrony przeniesienia, którego trzy wejścia, są dołączone do wejść argumentów operacji sumatora, oraz sumator równoległy, którego jedno wejście jest dołączone do wyjścia sumy a drugie do wyjścia przeniesienia sumatora ochrony przeniesienia, przy czym jedno wyjście sumatora równoległego jest dołączone do wyjścia wyniku sumatora. Dalsze korzyści z wynalazku uzyskuje się, gdy dwa z trzech wejść argumentów operacji jednostki arytmetyczno-logicznej są dołączone do trzech pierwszych układów logicznych, które to układy są następnie dołączone' go jednego z trzech wejść argumentów operacji sumatora. Pierwszy z trzech- pierwszych układów logicznych jest elementem I, drugi jest elemenetem LUB zaś trzeci jest elementem ALBOKolejne korzyści z wynalazku uzyskuje się, gdy jednocz trzech wejść argumentów operacji jednostki arytmetyczno-logicznej i wyjście wyniku są dołączonne do trzech drugich układów logicznych, które to układy są następnie dołączone do wyjścia jednostki arytmetyczno-logicznej. Pierwszy z trzech drugich układów logicznych jest elementem I, drugi jest elementem LUB zaś trzeci jest elementem ALBO.

Następne korzyści uzyskuje się, gdy zgodnie z wynalazkiem dwa z trzech wejść- argumentów operacji jednostki arytmetyczno-logicznej są dołączone do pierwszego multipleksera, który jest następnie dołączony do trzech pierwszych układów logicznych, trzy pierwsze układy logiczne są dołączone do drugiego multipleksera, który jest następnie dołączony do jednego z

165 457 trzech wejść argumentów operacji sumatora, albo gdy trzy drugie układy logiczne są dołączone do wyjściowego multipleksera, który jest następnie dołączony do wyjścia jednostki arytmetyczno-logicznej, przy czym układ przełączający zawiera multiplekser przekazujący zawartość rejestrów uniwersalnych do trzech wejść argumentów operacji jednostki arytmetyczno-logicznej.

Zaletą rozwiązania według wynalazku jest to, że umożliwia ono wykonywanie instrukcji równolegle celem podniesienia wydajności istniejącego komputera. Układ według wynalazku zmniejsza zwłokę wykonywania instrukcji wynikającej z zatorów powodowanych przez zależności danych w wykonywanych instrukcjach oraz eliminuje blokady spowodowane zatorami wynikająymi z zależnoci danych, istniejącymi pomiędzy instrukcjami wykonywanymi równolegle.

Przedmiot wynalazku jest uwidoczniony w przykładach wykonania na rysunku, na którym fig. 1 przedstawia znaną architekturę do wykonywania instrukcji, tworzącą pary operacji, fig.2 zespół sekwencji czasowych, które przedstawiają wykonywanie potokowe instrukcji skalarnych, fig.3 - schemat blokowy sumatora, który odbiera do trzech argumentów i wytwarza pojedynczy wynik, fig.4A i 4B - podział na kategorie instrukcji wykonywanych przez daną maszynę skalarną, fig.5 - funkcja wytwarzana w przypadku blokad, gdy zostają połączone instrukcje typu logicznego i typu sumowania kategorii z fig. 4A, fig. 6A i 6B - operacje, które muszą być wykonane na argumentach przez jednostkę arytmetyczno-logiczną według wynalazku celem realizacji instrukcji zawartych w kategoriach przedstawionych na fig. 4A i 4B, fig. 7A i 7B - marszrutę argumentów do jednostki arytmetyczno-logicznej według operacji z fig. 6A i 6B, fig. 8 - schemat blokowy układu według wynalazku ilustrujący równoległe wykonywanie dwu instrukcji blokujących się, fig.9 - schemat blokowy wielofunkcyjnej jednostki arytmetyczno-logicznej realizującej operacje określone przez fig. 6A, 6B, 7A i 7B, fig. 10 - funkcje realizowane w celu eliminowania blokad związanych z zatorami napotykanymi przy generacji adresów, fig. 11 schemat logiczny przedstawiający wielofunkcyjnąjednostkę arytmetyczno-logiczną dla realizacji funkcji z fig. 10, fig. 12 - funkcje realizowane przez jednostkę arytmetyczno-logiczną w celu eliminowania blokad w złożonych instrukcjach rozgałęzienia, fig. 13 - schemat logiczny przedstawiający jednostkę arytmetyczno-logiczną dla realizacji funkcji z fig. 12 zaś fig. 14 przedstawia konfigurację sumatora wymaganą do eliminacji blokad dla instrukcji dotyczących dziewięciu argumentów.

W poniższym opisie termin cykl maszynowy odnosi się do faz potoku niezbędnych do wykonania instrukcji. Cykl maszynowy zawiera indywidualne przedziały, które odpowiadają stopniom potoku. Instrukcja skalarna jest instrukcją, która jest wykonywana z argumentami skalarnymi. Argumenty skalarne są to argumenty reprezentujące wielkości o jednej wartości. Termin Łączenie odnosi się do grupowania instrukcji zawartych w sekwencji instrukcji, grupowanie to odbywa się w celu współbieżnego lub równoległego wykonania zgrupowanych instrukcji. W przypadku minimalnym, łączenie jest reprezentowane przez łączenie w pary dwu instrukcji celem równoczesnego wykonania. W niniejszym wynalazku, łączone instrukcje posiadają postać niezmienioną w porównaniu z postacią, które posiadały w przypadku wykonywania skalarnego. Jak wyjaśniono poniżej, instrukcjom składanym towarzyszą znaczniki to znaczy bity do zgrupowanych instrukcji, które zaznaczają grupowanie instrukcji do równoległego wykonywania. Bity te wskazują początek i koniec instrukcji złożonej.

Poniżej zostanie opisane ulepszone rozwiązanie sprzętowe, służące do eliminacji blokad jednostek wykonawczych, które nie mogą być usunięte przy zastosowaniu znanego stanu techniki. Celem zastosowania ulepszonego rozwiązania jest zminimalizowanie wymagań sprzętowych dla usunięcia tych blokad i do nakładania na czas cyklu jedynie umiarkowanego lub żadnego obciążenia związanego z dodatkowym sprzętem. Dla wdrożenia tego rozwiazania nie są wymagane zmiany architektury i z tego względu jest utrzymana zgodność kodu wynikowego dla instniejącej architektury komputera.

Zbiór instrukcji dla instniejących architektur skalarnych Systemu/370 jest znany z przytoczonych w stanie techniki publikacji. Instrukcje te są instrukcjami skalarnymi pod tym względem, że są wykonywane przez operacje na argumentach skalarnych. Poniżej podane są

165 457 odniesienia do poszczególnych instrukcji w zbiorze instrukcji wykonywanych przez opisane powyżej maszyny w zwykłej postaci na poziomie asemblera.

Załóżmy, że następująca sekwencja instrukcji ma być wykonana przez maszynę superskalarną, mającą możliwość wykonywania czterech instrukcji w cyklu:

Tabela 3 (1) LOAD R1, X załaduj zawartość X do R1 (2) ADD R1, R2 dodaj Rj do R2 i przelijj wynik do RI (3) SUB R1, R3 odejmjj 133 do R j j przelijj wynik do R1 (4) STORE R1, Y zapizz wynik w komórce pamięć i Y

Mimo możliwości wykonywania wielokrotnej instrukcji w cyklu, maszyna superskalarna będzie wykonywać powyższą sekwencję szeregowo ponieważ instrukcje blokują się wzajemnie. Stwierdzono w oparciu o analizę śladu, że blokady występują w jednej trzeciej części czasu. Z tego względu znaczna część możliwości maszyny superskalarnej będzie marnotrawiona, powodując obniżenie wydajności uzyskanej dzięki superskalarności. Wydajność maszyny superskalarnej z zablokowanymi instrukcjami superskalarnymi jest przedstawiona przez sekwencję czasową 8 na figurze 2, gdzie zakłada się, że struktura potoku dla instrukcji z tabeli 3 jest następująca:

(1) LOAD: ID AG CA PA (2) i (3) ADD i SUBTRACT: ID EX PA, gdzie ID jest zdekodowaniem instrukcji i dostępem do rejestru, AG jest wytworzeniem adresu argumentu, CA reprezentuje dostęp do pamięci podręcznej, EX przedstawia wykonanie i PA (odeślij) przedstawia zapis wyniku do rejestru. Dla uproszczenia, zakłada się, że we wszystkich przykładach podanych w tym opisie nie jest zrealizowane obejście, chyba że jest to wyraźnie stwierdzone. W maszynie superskalarnej wykonanie strumienia instrukcji odbywa się szeregowo, ze względu na blokowanie instrukcji, zmniejszające efektywność maszyny superskalarnej do poziomu efektywności maszyny skalarnej. Na fig. 2, instrukcje (2) i (3) nie wymagają generacji adresu AG. Jednakże, ten stopień potoku musi być uwzględniony. Stąd nieoznaczone przedziały. Konwersja ta działa także dla innych trzech sekwencji na fig. 2.

Powyższy przykład pokazuje, że blokowanie się instrukcji może ograniczać równoległość możliwą do uzyskania na poziomie instrukcji do stosowania przez maszynę superskalarną. Działanie jej może być polepszone wraz z przetwarzaniem potokowym i bocznikowaniem wyników jednej zablokowanej instrukcji do drugiej, niezależnie od tego, wykonanie zablokowanych instrukcji musi być szeregowe.

Jeżeli należy uniknąć strat cykli wykonania wynikłych z blokad, zablokowane instrukcje muszą być wykonywane równolegle i widziane jako pojedyncza instrukcja. To prowadzi do koncepcji składanej instrukcji zablokowanej, zbioru instrukcji skalarnych, które powinny być traktowane jako pojedyncza prosta instrukcja, mimo wystąpienia blokad. Pożądaną cechą sprzętu wykonującego instrukcję składaną jest to, aby jej wykonanie wymagało nie więcej cykli niż to wymaga wykonanie jednej instrukcji składanej. Jako konsekwencja składania instrukcji i jej pożądanych charakterystyk. Maszyna pracująca ze zbiorem instrukcji złożonych musi widzieć instrukcje skalarne przez zastosowanie sprzętu, a nie opis kodu operacji.

Koncepcje składanych zablokowanych instrukcji mogą być wyjaśnione przy zastosowaniu instrukcji ADD i SUB w tabeli 3. Te dwie instrukcje można widzieć jako typ instrukcji pojedynczej, ponieważ stosują one ten sam sprzęt. W wyniku tego mogą być one połączone i wykonane jako jedna instrukcja. Celem wykorzystania równoległości ich wykonanie wymaga wykonania:

R1 =R1 + R2 -R3

165 457 w jednym cyklu zamiast wykonania sekwencji:

R1 = R1 + R2 R1 = R1 -R3, która wymaga do wykonania więcej niżjednego cyklu. Blokada może być wyeliminowana, ponieważ sumowanie i odejmowanie wykorzystuje identyczny sprzęt. Ponadto, przez zastosowanie jednostki arytmetyczno-logicznej, która wykorzystuje sumator ochrony przeniesienia i sumator równoległy, jak pokazano na figurze 3, złożona instrukcja R1 + R2 - R3 może być wykonana w jednym cyklu.

Jest oczywiste, że połączona postać (R1 + R2 - R3) odpowiada przepisaniu dwóch argumentów dnigiej instrukcji w terminach trzech argumentów, co wywołuje potrzebę zastosowania sumatora, który może wykonywać drugą instrukcję w odpowiedzi na trzy argumenty.

Na fig. 3 jest pokazany sumator ochrony przeniesienia 10, który jest konwencjonalny pod wszystkimi względami, odbiera trzy argumenty celem wytworzenia dwóch wyników, sumy S na wyjściu 12 i przeniesienia C na wyjściu 14. W przykładzie tym, wejścia 10A, 10B, 10C sumatora ochrony przeniesienia 10 odbierają argumenty zawarte w trzech rejestrach R1, R2 i R3 (dopełnione). Wyjścia sumatora ochrony przeniesienia 10 są podawane na stopień 16 oraz na stopień 17 w celu podawania wartości przeniesienia za pomocą wejścia 20 sterowanego przez 1 i 0 (gorąca 1 lub 0). Wartość wejścia 20 jest ustawiona konwencjonalnie opowiednio do funkcji, którą ma wykonywać sumator ochrony przeniesienia 10.

Wyjście sumy i przeniesienia (z dołączoną 1 lub 0) sumatora ochrony przeniesienia 10 tworzą dwa wejścia sumatora równoległego 22, który odbiera także konwencjonalnie gorącą 1 lub 0 na wejściu 24 odpowiednio do wymaganej operacji i wytwarza wynik 26. Na fig.3 wynik wytworzony przez sumator równoległy 22 jest połączeniem zawartości trzech rejestrów R1, R2 i R3 (dopełnienia).

Chociaż dodawanie trzech argumentów na jeden wynik wymaga dodatkowego stopnia, sumatora ochrony przeniesienia na fig.3, na krytycznej ścieżce jednostki arytmetyczno-logicznej, taki stopień nie powinien pogarszać czasu cyklu maszyny, ponieważ długość innych ścieżek zwykle przekracza długość dla jednostki arytmetyczno-logiczej. Te krytyczne ścieżki zwykle znajdują się wśród ścieżek zawierających dostęp do tabeli, generację adresów, która wymaga jednostki arytmetyczno-logicznej trzy do jednego i połączenia pomiędzy podzespołami. Z tego względu dodatkowe opóźnienie stopnia nie jest niedopuszczalne i efektem proponowanego układu będzie polepszenie działania w porównaniu z maszyną skalarną lub superskalarną. Podniesienie wydajności jest pokazane na fig.2 przez grupę wykresów 26 dotyczących przetwarzania potokowego. Te wykresy pokazują wykonanie sekwencji omawianych instrukcji przez maszynę o zbiorze instrukcji złożonych, która zawiera jednostkę arytmetyczno-logiczną z sumatorem o konfiguracji przedstawionej na fig.3.

Jak pokazano na wykresach czasowych 8 i 26 z fig.2, wykonanie sekwencji przez maszynę o zbiorze instrukcji złożonych wymaga ośmiu cykli lub dwu cykli na instrukcję w porównaniu z 11 cyklami 2,75 cyklami na instrukcję, dającymi się uzyskać przez maszyny skalarne i superskalarne. Jeżeli zakłada się realizację bocznikowania we wszystkich maszynach, zestawy wykresów 28 i 30 z fig.2 opisują wykonanie dające się uzyskać odpowiednio w maszynach skalarnych lub superskalarnych i maszynach o zbiorze instrukcji złożonych. Z tych urządzeń, maszyna superskalarna wymaga ośmiu cykli lub dwu cykli na instrukcję dla wykonania przykładowego kodu, podczas gdy maszyna o zbiorze instrukcji złożonych wymaga sześciu cykli lub 1,5 cykli na instrukcję. Należy odnotować przewagę maszyny o instrukcjach łączonych nad susperskalarną i skalarną przy braku przewagi maszyny superskalarnej nad skalarną dla przyjętej sekwencji instrukcji.

Łączenie instrukcji z ich jednoczesnym wykonaniem sprzętowym nie jest ograniczone do operacji arytmetycznych. Na przykład, większość operacji logicznych może być złożona w sposób analogiczny do operacji arytmetycznych. Również większość operacji logicznych może być złożona z operacjami arytmetycznymi. Łączenie pewnych intrukcji mogłoby jednak powodować rozciąganie czasu cyklu, ponieważ z wykonaniem złożonych funkcji jest związane nie

165 457 dające się zaakceptować opóźnienie. Na przykład, złożona instrukcja ADD-SHIFT może rozciągać niedopuszczalnie czas cyklu, co spowoduje utratę całego zysku wydajności. Częstotliwość blokad pomiędzy tymi instrukcjami jest jednak niska ze względu na niską częstotliwość występowania instrukcji przesuwania, z tego względu mogą być one wykonywane szeregowo bez zasadniczego obniżenia wydajności.

Jak opisano powyżej, blokady wynikające z zatorów danych występują, gdy do rejestru lub komórki pamięci jest zapisywana, a następnie odczytywana kolejna instrukcja. Proponowany układ według wynalazku eliminuje te blokady przez tworzenie nowych funkcji, które powstają z połączenia wykonania instrukcji, których argumenty przedstawiają zatory danych, podczas gdy wykonywanie funkcji jest zawarte w zbiorze instrukcji. Chociaż występowanie pewnych kombinacji instrukcji i argumentów nie jest oczekiwane w działającym programie, rozważane są wszystkie kombinacje. W przypadku ogólnym byłyby zrealizowane wszystkie funkcje otrzymane na podstawie powyższej analizy, jak również fimkcje wynikające ze skalarnej realizacji zbioru instrukcji. W praktyce, jednak powstają pewne funkcje, których realizacja niezbyt dobrze nadaje się do schematu proponowanego do tego układu. Poniższe przedstawienie wyjaśnia te koncepcje przez omówienie, jak powstają nowe funkcje z połączenia wykonania dwu instrukcji. Przykłady sekwencji instrukcji, które są dobrze obsługiwane według wynalazku są przedstawione razem z pewnymi sekwencjami, które nie są dobrze obsługiwane.

Przykład wyprowadzania instrukcji równolegle można znaleźć w znanej maszynie superskalarnej. Zastosowanie to ułatwia równoległe wykonywanie wyprowadzanych instrukcji, w których ma miejsce blokada. Zastosowanie sprzętu eliminującego zależność danych według wynalazku nie jest jednak ograniczone do szczególnego rozwiązania i architektury wykonania, ale jest stosowane na ogół do układów, gdzie realizuje się wielokrotne instrukcje w cyklu.

Aby stworzyć bazę sprzętową do niniejszego opisu zakłada się architekturę na poziomie instrukcji Systemu/370, w której można wyprowadzać do dwu instrukcji na cykl. Przyjęcie tych założeń nie ogranicza jednak ani koncepcji architektury Systemu/370 ani dwudrożnej równoległości. Omawianie jest podzielone na części dotyczące działania jednostki arytmetyczno-logicznej, generacji adresu pamięci i określenia rozgałęzienia.

Zbiór instrukcji Systemu/370 może być podzielony na kategorie instrukcji, które mogą być wykonywane równolegle. Instrukcje w obrębie tych kategorii mogą być łączone lub składane w instrukcję złożoną. Poniżej opisany układ według wynalazku realizuje wykonanie instrukcji złożonych równolegle i zapewnia, że blokady istniejące pomiędzy elementami instrukcji złożonej będą usuwane podczas jednoczesnego wykonywania instrukcji. Na przykład, architektura Systemu/370 może być podzielona na te kategorie przedstawione na figurach 4A i 4B.

Zasada tej kategoryzacji była oparta na wymaganiach funkcjonalnych instrukcji Systemu/370 i ich wykorzystania sprzętowego. Pozostałe instrukcje Systemu/370 nie są uważane za złożone przy ich wykonywaniu według niniejszego opisu. Nie wyklucza to ich łączenia w przyszłej maszynie o instrukcjach złożonych i ewentualnego zastosowania wniosków co do unikania blokad przedstawionych w niniejszym opisie.

Rozważmy instrukcje zawarte w kategorii 1, złożone z instrukcji tej samej kategorii, jak w przykładzie następującego ciągu instrukcji:

Ar R1, R2

SR R3, R4

Sekwencja ta, wolna od blokad uzależnienia danych, daje wyniki:

R1 = R1 +R2 R3 = R3 + R4, które zawierają dwie niezależne instrukcje określone przez architekturę na poziomie instrukcji. Wykonanie takiego ciągu wymagałoby zastosowania dwu niezależnych i równoległych jednostek arytmetyczno-logicznych typu dwa do jednego, zaprojektowanych dla architektury na poziomie instrukcji. Wyniki te mogą być uogólnione na wszystkie pary sekwencji instrukcji, wolne od blokad wynikających z zatorów danych, w których obie instrukcje określają operację jednostki arytmetyczno-logicznej. Dwiejednostki arytmetyczno-logiczne są wystarcza10

165 457 jące do wykonania instrukcji podawanych parami, ponieważ każda instrukcja określa przynajmniej jedną operację jednostki arytmetyczno-logicznej.

Wiele sekwencji instrukcji nie jest jednakże wolnych od blokad wynikających z zatorów danych. Te blokady danych prowadzą do zatamowania potoku, które obniża wydajność w typowym przetwarzaniu potokowym. Pewnym rozwiązaniem dla zwiększenia wydajności procesora jest wyeliminowanie tych zatorów z potoku przez zastosowanie pojedynczej jednostki arytmetyczno-logicznej, która może usunąć blokady zatorów danych. Celem wyeliminowania tych blokad jednostka arytmetyczno-logiczna musi wykonywać nowe funkcje, które wynikają z łączenia w pary instrukcji i konfliktów argumentów. Wynikowe funkcje zależą od określonych operacji jednostki arytmetyczno-logicznej, sekwencji tych operacji, i konfliktów argumentów pomiędzy operacjami. Wszystkie sekwencje instrukcji, które mogą być wytworzone przez instrukcje łączenia w pary, które są zawarte w liście instrukcji łączonych, podanej wcześniej w tej części, i będą określać działanie jednostki arytmetyczno-logicznej, muszą być analizowane dla wszystkich możliwych konfliktów argumentów.

Ogólne ramy dla likwidacji blokad według wynalazku zostały zaprezentowane powyżej, gdzie jest przedstawiony bardziej konkretny przykład analiz, które należy wykonać przy określaniu wymagań na jednostkę arytmetyczno-logiczną eliminującą blokady. Załóżmy istnienie sumatora typu trzy do jednego, jak opisano powyżej w odniesieniu na fig.3. Niech OP1 i OP2 przedstawiają odpowiednio pierwszą i drugą wykonywaną operację. Na przykład, dla następującego ciągu instrukcji,

NR R1, R2

AR R3, R4

OP1 odpowiada operacji NR, podczas gdy OP2 odpowiada operacji AR (patrz niżej na opis tych operacji). Niech AIO, ALI i AI2 przedstawiają wejście odpowiadające odpowiednio (R1), (R2), (R3) sumatora typu trzy do jednego z fig.3. Rozważmy analizę składania zbioru instrukcji (NR, OR, XR, aR, ALR, SLR, SR), podzbioru kategorii 1, według fig. 4A i 4B. Operacje tego zbioru instrukcji są określone przez:

NR bitowe logiczne I przedstawiane przez A

OR bitowe logiczne LUB przedstawiane przez V

XR bitowe LUB wykluczające przedstawiane przez ®

AR 32 bitowe dodawanie ze znakiem przedstawiane przez +

ALR 32 dodawanie bez znaku przedstawiane przez +

SR 32 bitowe odejmowanie ze znakiem przedstawiane przez SLR 32 bitowe odejmowanie bez znaku przedstawiane przez Ten zbiór instrukcji może być podzielony dla dalszych rozważań na dwa zbiory. Pierwszy zbiór zawierałby instrukcje logiczne NR, OR i XR, a drugi zbiór zawierałby instrukcje arytmetyczne AR, ALR, SR i SLR. Zgrupowanie instrukcji arytmetycznych może być uzasadnione następująco. AR i ALR mogą być widziane jako efekt 33 bitowego dodawania z dopełnieniem binarnym przy zastosowaniu rozszerzenia o znak dla AR i rozszerzenia o O dla ALR i podaniu gorącego O do sumatora. Aczkolwiek ustawienie kodu warunki i przepełnienia są jedynie dla każdej instrukcji, operacja wykonywana przez sumator, dodawanie dwójkowe, jest wspólna dla obu instrukcji. Podobnie, SR i SLR mogą być widziane jako wynik 33 bitowego dodawania z dopełnieniem binarnym przy zastosowaniu rozszerzenia o znak dla SR o rozszerzenia o O dla SLR i podanie gorącego 1 do sumatora. Inwersja odjemnika odbywa się na zewnątrz sumatora. Ponieważ te cztery operacje arytmetyczne wykonują zasadniczo tę samą operację, dodawanie dwójkowe, będą one określane jako instrukcje typu ADD, podczas gdy operacje logiczne będą określane jako instrukcje typu LOGICAL.

W wyniki zredukowania powyższego zbioru instrukcji do dwu operacji, należy rozważyć poniższe sekwencje operacji dla przeanalizowania składania tego zbioru instrukcji:

LOGICAL po którym następuje ADD

ADD pp którym następujeLOGICAL

LOGICAL po którym następuje LOGICAL

ADD po którym następuje LOGICAL.

165 457

Dal każdej z tych sekwencji należy rozważyć wszystkie kombinacje rejestrów. Liczba kombiacji odpowiada następującej sytuacji: wszystkie cztery opisy rejestrów są różne plus 1) dwa są takie same; 2) trzy są takie same; i 3) cztery są takie same. Liczba kombinacji może być stąd wyrażona jako:

Liczba kombinacji = 1 + 4^ci i=2 gdzie symbol _nC_r przedstawia liczbę kombinacji rzn. Ponieważ _nC_r = n!/((n-r)!r!), ze wzorów tych można ptoeślić hczbę ^ηιόίηπϊ na 12. Te 12 kombinncji rejestrów ^rest następu^ce :

j.Rj*R2*R3*R4 2. R1*R2;ćR3*R4 2. R2=R2lRHR4

4. R2=R4nR1nR3

5. R2=R3lR1lR4

6. R2=R5=R4nRl

7. R1=R4iR4iR2

8. R1=R4nR2nR3

9. R1=R4=R2lR4

10. R1=R2=R4iR3

11. R1=R3=R4^R2

H. R1=R2nR3nR4.

Jedy1ie kombinac5e od siódmej do dwunastej przyczyniają się do wzrostu blokad zależności Jedynie Fomcęin wy twdrzane przez powyższo przópapkr blokad dlo sęówencji LOG1CALBDD wnlichone nowe wj sw ppnnoe na zipow^ 5z odzńe ρnrΓacie typu LOGiwAL c ą oznaczone przez w ΐ ORzoncj e twpu oCDD są nnear:none rzaes gPodozar jdy fig. 0 ZDeUstzwlc ooatecia. które muszą być wykonane na argumentach instrukc^ tmu ADD i typp LOGICAL ηeiren eliminacji Ulokdby fi gwyo 6A t dB pnroUstawląjh operuote jedpu sOzi dc Ιπ^ιηοη^^^,.^ waπmcnae do wakonania na we7ściecó leeWwilni ηrytmciacarτ-tooidnnjj Aty, Bo- o AI2 celwm hnolinacri węyoηTnτh zawiodnch w naiehoriach ήπ^ο^ί j ąozon yoh nc Oa- 4A ikB. Nz figi wA ϊ 6B jhdnothaowrplowy ϊππι^ wskozuja hdupełuienie dwójkawe i (x) 5okaz5je wartość bozwzględną x. Tm jf^om zm^s^s wbudowana na j^ł^^o^^wiz i dentyczooi dj dęwyηszdj, jzępok ZtU' roaważone 1 ącoema wsudηW:ich meżiiwzch ko1aoerir. Dla of^eazoji z fig.5, wtóre maje dna wykinroie pażaT j edapatka w·zimetyahnh-logicdahi ntaoowaniz eednoetną Dyk6nowrah musi kiwrewać Tąpm. cawartoIη aejestrów zo odooRinUnizh węęeOjejinorOg orytmotooαwo-iugiczneI. Fiowak 7 A d 7B pnWsumoranjz rówow ai^ip iwgomcntów, które powimy wj/styam dlo ΟεώιοηΟη oτrdnetyc8go-tηdiahhej wlτeślonet wnniacnymi an ów, OA i pB dln węeoąewadiα 0-0^00 a fig.5. Rznηm o tómi ηterunηnmi ηejłaCc podane (nstiuOcje tygu LOGyCAL i WB)D opOrm cłótwienid ynwzhdowd^ia tyah wirników na fir, oAiOB. KraIunkieta pnwnych InczoO ADO-ADu niw zostefy uwηgtęWnloπϊ, hwninwnż to aperrtjo wgmagałaroddonPo cBdmetyczno-jzizzpej z cztairech weaśęiach.

.reji ożzywieje. aCe ęczhniwiąn kotyehcαhjowy opls -^-^ιι,^ϊοϊ się za rozwężnnip analizy instrukaji ztaZewei ar cztaazoo γ^οοΙ^^ Raz Row R4 wuporzyitame wpwaiazku nie ^jesy ingrukaione donzienn azc^^^^<hlnjch . WybRr tR^h weranizeeIl jco t ΐαΟγίΜβ pu mocą w ηnolniai zrozumieniu. W jzaonywijtości an;nicameże ry^y uooOłnioaói c w wy nikyoo owkhηcRW nównrci.

Cchemat blokowy przedstawiający układ według wynalazku, realizujący operacje opisane na fig. RA, ΟΒι 7A o wB t pesi p^dstaw^ny na figura wy odziz rejroa I·onUaeów Sa cOtηemura ins trokcto zltiowo zc wiernOsc p molrukcjc zaeτancw mOe^o- paminaż 52 o 5k. Ποϊοπε ηesrdlkaja posradają óotżηouzn ^acną,^ Ζ8ρίΐ3ηο w iznojaęh znaaan ików 56 i 5 6. TernUakrye u anO zozcnmki ro podane Ta óOłodu toziczncwo bO dhkpOnwociów sttrow9nia, iisty dnOodujh mslm0cIc i e zawarte w ich cnaoarηd7ch retem ηwdawapiz ο^οΤρ w ybóry fkaioji na

165 457 wyjścia 66. Sygnały wyboru rejestru na wyjściu 62 ustawiają układ ptezłcceający 64, który jest połączony z rejestrami uniwersalnymi 63 celem podawania zawartości maksymalnie trzech rejestrów do trzech wejść AI0, AU i AI2 argumentów operacji jednostki arytmetyczno-logicznej 65 eliminującej zależność danych. Jednostka arytmetyczno-logiczna 65 jest wielofunkcyjną jednostką arytmetyczno-logiczną, której funkcja jest wybierana przez sygnały wyboru funkcji dane na wyjściu 66 układu logicznego 60 dekodującego i sterującego. Przy użyciu argumentów podawanych z rejestrów, połączonych przez układ przełączający 64, jednostka arytmetycznologiczna 65 będzie wykonywać funkcje wskazywane przez sygnały wyboru funkcji, wytwarzając wynik na wyjściu 67.

Równolegle z opisaną powyżej jednostką arytmetyczno-logiczną działa druga jednostka arytmetyczno-logiczna, zawierająca następny układ logiczny 40 dekodowania i sterowania, który dekoduje pierwszą instrukcje zapisaną w pierwszej tabeli pamięci 52 celem podania sygnałów wyboru rejestru na wyjściu 41 do następnego układu przełączającego 42, który jest także połączony z rejestrami uniwersalnymi 63. Układ logiczny 40 podaje także sygnały wyboru funkcji na wyjściu 44 do dmpargpmentomzj jednostki arytmetyczno-logicznej 45, wytwarzającej wynik na wyjściu 47. Jednostka arytmetyczno-logiczna 45 jest zastosowana w celu wykonywania instrukcji zapisanej w pierwszej tabeli pamięci 52, podczas gdy druga instrukcja zapisana w drugiej tabeli pamięci 54 jest wykonywana creez jednostkę arytmetyczno-logiczną 65. Jak opisano poniżej, jednostka arytmetyczno-logiczna 65 może wykonywać drugą instrukcję, której jeden argument zależy lub żaden argument nie zależy od danych wynikowych, wytwarzanych przez wykonanie pierwszej instrukcji. Obie jednostki arytmetyczno-logiczne z tego względu działają równolegle, zapewniając współbieżne wykonanie dwu instrukcji złożonych lub nie.

Zakłada się że istnieje element łączący, który to element łączy w pary lub składa instrukcje ze strumienia instrukcji, eemietajączgo sekwencje wejść skalarnych instrukcji, do skalarnej maszyny liczącej, w której jest on obecny. Element łączący grupuje instrukcje odpowiednio do powyższej dyskusji. Na przykład, instrukcje kategorii 1(fig.5) są zgrupowane w pary logiczno/sumecyjnz, spmacyjno/logiczne, logiczno/logiczne i sumacyjno/spmecyjne. Do każdej instrukcji ze zbioru instrukcji złożonych dodany jest znacznik eamietejccy informację sterującą. Znacznik eamiere bity łączone, które odnoszą się do części znacznika stosowanego specjalnie do identyfikacji grup instrukcji łączonych. Korzystnie, w przypadku składania dwu instrukcji, stosowana jest następująca prcedpta do wskazywania, gdzie ma miejsce łączenie. W komputerach System/370 wszystkie instrukcje są uszeregowane na granicy półsłowa i ich długości wynoszą 2,4 lub 6 bajtów. W tym przypadku dla każdej połówki słowa konieczny jest znacznik łączenia. Znacznik jednobitowy jest wystarczający do wskazania czy instrukcja jest czy też nie jest złożona. Korzystnie, 1 wskazuje, że instrukcja rozpoczynająca się rozważanym bajtem łączy się z następujących po niej instrukcji. 0 wskazuje brak łączenia. Bit łączenia skojarzony z półsłowami, które nie zawierają pierwszego bajtu instrukcji, jest ignorowany. Bit łączenia dla pierwszego bajtu drugiej instrukcji jest także ignorowany. W konsekwencji wymagany jest tylko jeden bajt informacji do zidentyfikowania i odpowiedniego wykonania instrukcji złożonych. Stąd, bity znaczników zawarte w tabelach znaczników 56 i 58 są wystarczające do informowania układu logicznego 60 dekodującego i sterującego, że instrukcje zawarte w tabelach pamięci 52 i 54 mają być składane, to jest wykonywane równolegle. Układ logiczny 60 dekodowania i sterowania sprawdza następnie instrukcje zapisane w tabelach pamięci 52 i 54 celem określenia jaka jest sekwencja ich wykonania, jakie warunki blokady, czy ona występuje i jakie działanie jest potrzebne. Określenie to jest przedstawione dla instrukcji kategorii 1 na fig.5. Logika dekodowania i sterowania określa także działanie konieczne do eliminacji dowolnej blokady zależności danych, jak na fig. 6A i 6B. Te tryby określenia są zebrane na fig. 7A i 7B. Na fig. 7A i 7B, przy założeniu, że układ logiczny 60 dekodowania i sterowania określił na podstawie bitów wyróżniających, że instrukcje w tabelach pamięci 52 i 54 mają być składane. Układ logiczny 60 wysyła sygnał wyboru funkcji na wyjściu 66, wskazujący żądaną operację według skrajnej lewej kolumny fig. 7a. Kody OP instrukcji są w sposób bezpośredni eaerodomane, dając na wyjściu wyboru funkcji, określoną operację w kolumnach oznaczonych OP1 i OP2 na fig. 7A i 7B. Sygnały wyboru rejestrów na wyjściu 62 wybierają rejestry na fig.8 za pomocą układu przełączającego 64, jak to jest wymagane w kolumnach A10, AI1 i AI2 na fig. 7A i 7B.

165 457

Zatem załóżmy, że pierwsza instrukcja z tabeli pamięci 52 jest ADD R1, R2 i że druga instrukcja jest ADD R1, R4. Osiemnasta linia na fig. 7A pokazuje operację jednostki arytmetyczno-logicznej 65, którą układ logiczny 60 dekodowania i kontroli wskazuje przez OP1 = + i OP2 = +, podczas gdy rejestr R2 jest łączony do wejścia AI0, rejestr R4 do wejścia AI1 a rejestr R1 do wejścia Al2.

Figura 9 przedstawia strukturę i działanie jednostki arytmetyczno-logicznej, eliminującej zależności danych. Na fig.9 jest pokazany sumator trój argumentowy 70 o pojedynczym wyniku, odpowiadający sumatorowi z fig.3. Sumator 70 ma wejścia 70a, 70b, 70c połączone z wejściami A10, AI1 i AI2 argumentów operacji jednostki arytmetyczno-logicznej 65. Z wejścia AI2, argument jest kierowany przez trzy pierwsze układy logiczne 71, 72 i 73 odpowiadające odpowiednio logicznemu elementowi I, elementowi LUB i elementowi ALBO. Argument ten jest połączony w tych elementach logicznych z pewnym innym argumentem i skierowany do A10 lub AI1 odpowiednio do ustawienia pierwszego multipleksera 80. Drugi multiplekser 75 wybiera albo niezmieniony argument połączony z AI2 albo wyjście jednego z pierwszych układów logicznych 71,72 lub 73. Wejście wybrane przez drugi multiplekser 75 jest podawane do pierwszego inwertera 77 i trzeci multiplekser 78 łączy z jednym wejściem 70C sumatora 70 albo wyjście pierwszego inwertera 77 albo nieodwrócone wyjście drugiego multipleksera 75. Drugie wejście 70B sumatora 70 jest otrzymane z wejścia AU jednostki arytmetyczno-logicznej 65 za pomocą czwartego multipleksera 82, który wybiera albo 0 lub argument połączony z wejściem AU jednostki arytmetyczno-logicznej 65. Wyście czwartego multipleksera 82 jest odwracane przez drugi inwerter 84 i piąty multiplekser 85 wybiera albo odwrócone albo nie odwrócone wyjście czwartego mulipleksera 82 jako drugie wejście argumentowe do sumatora 70. Trzecie wejście 70A sumatora 70 jest uzyskane z wejścia A10, które jest odwrócone przez trzeci inwerter 87. Szósty multiplekser 88 wybiera albo O, argument do wejścia A10, albo jego odwrotność podawaną jako trzecie wejście 70A do sumatora 70. Wyjście jednostki arytmetyczno-logicznej 65 jest tworzone przez wyjściowy multiplekser 95, który wybiera wyjście 70D sumatora 70 lub wyjście jednego z drugich układów logicznych 90, 92 lub 93. Drugie układy logiczne 90, 92 i 93 łączą wyjście sumatora 70 za pomocą wskazywanych operacji logicznych z wejściem AI1 argumentu operacji.

Jest oczywiste, że sygnał wyboru funkcji zawiera zasadniczo sygnały wyboru multipleksera A, B, C, D, E, F, G i gorące wejście wyboru I/O do sumatora 70. Sygnały wyboru multipleksera mają zakres od pojedynczego bitu dla sygnałów A, B, E i F do dwubitowych sygnałów dla C, D i G.

Stany złożonego sygnału sterowania (A,B,C,D,E,F,G,I/O,VO) są łatwe do określenia na podstawie fig.7A i 7B. Na przykład, według powyższego przykładu ADD R1, R2 ADD R1, R4, sygnał OPl zstawiałby sygnał mulipleksera C na wybór sygnału obecnego na AI2, podczas gdy sygnał F wybierałby nieodwracające wyjście drugiego mulipleksera 75, dzięki czemu podawany jest argument w R1 na najbardziej prawe wejście sumatora 70. Podobnie, sygnały multipleksera B i E byłyby ustawione tak, aby dawać argument na AU w postaci nieodwróconej na środkowe wejście sumatora 70, podczas gdy sygnał multipleksera D byłby ustawiony na podawanie argumnetu A10 na skrajne lewe wejście sumatora 70, bez inwersji. Ostatecznie, dwa wejścia I/O są ustawione odpowiednio do tych dwu .operacji dodawania. W przypadku tych wejść, wyjście sumatora 70jest prostą sumą trzech argumentów, które odpowiadają żądanemu wyjściu jednostki arytmetyczno-logicznej. Z tego względu, sygnał,sterowania G byłby ustawiany tak, że wyjściowy multiplekser 95 wyprowadzałby wynik utworzony przez sumator 70, który byłby sumą argumentów w rejestrach R1, R2 i R3.

Podczas łączenia instrukcji w sekwencje logiczno/sumacyjne, funkcja logiczna byłaby wybrana przez drugi multiplekser 75 i podana przez trzeci multiplekser 78 do sumatora 70, podczas gdy dodawany argument do operacji logicznej byłby prowadzony przez jeden z multiplekserów 85 lub 88 dojednego z innych wyjść sumatora70, przy czym O jest poddawane do trzeciego wejścia. W tym przypadku, wyjściowy multiplekser 95 byłby ustawiany do wybrania wyjścia sumatora 70 jako wyniku.

Ostatecznie, w złożonej sekwencji sumacyjno/logicznej, dwa argumenty mają być dodane najpierw, będą doprowadzone do dwóch wejść sumatora 70, podczas O będzie podane do

165 457 trzeciego wejścia. Wyjście sumatora 70 jest natychmiast łączone z nie wybranym argumentem w drugich układach logicznych 90, 92 i 93. Sygnał sterowania G będzie ustawiony tak, aby wybierać wyjście tego układu, którego działanie odpowiada drugiej instrukcji zbioru instrukcji złożonych.

Podczas tworzenia sieci działań, opartej na fig.9, podjęto decyzję nie utrzymywania blokad, w których wynik pierwszej instrukcji jest stosowany jako oba argumenty drugiej instrukcji. Ta reprezentacja powoduje, że inne operacje wymagane przez składanie lOgICALADD mogą być określane przez porównanie sieci działań z kolumną funkcji z fig.5. W tej kolumnie po operacji typu LOGICAL na dwóch argumentach następuje operacja typu ADD pomiędzy wynikiem LOGICAL a trzecim argumentem. Jest to wykonywane przez kierowanie argumentów do połączenia logicznego do AI0 i AI2 na fig. 9 i przez odpowiednie z pierwszych układów logicznych 71,72 lub 73, kierowanie tego wyniku do sumatora 70 i kierowanie trzeciego argumentu przez AI1 do sumatora 70. Inwersje i poddawanie gorącej 1 lub 0 są traktowane jako część sygnału wyboru funkcji , jak tego wymaga określona operacja arytmetyczna. W innych przypadkach, po operacji typu ADD pomiędzy dwoma argumentami następuje operacja typu LOGICAL pomiędzy wynikiem typu ADD i trzecim argumentem. Jest to realizowane przez kierowanie argumentów dla operacji typu ADD do wejść A10 i AI2, kierowanie tych wejść do sumatora 70, kierowanie wyjścia sumatora 70 do drugich układów logicznych 90, 92 i 93 i kierowanie trzeciego argumentu przez AI3 do tychże układów logicznych umieszczonych po sumatorze 70. Operache typu LOGICAL po których następują operacje typu LOGICAL są wykonywane przez kierowanie dwóch argumentów dla pierwszego typu LOGICAL do wejść A10 i AI2, które są kierowane do układów logicznych 71, 72, 73 znajdujących się przed sumatorem 70, kierowanie wyników z tych układów logicznych znajdujących się przed sumatorem 70 przez jednostkę arytmetyczno-logiczni^S, bez modyfikacji, polegającej na dodawaniu do zera do układów logicznych 90, 92, 93 za sumatorem 70 i kierowanie trzeciego argumentu przez AI3 do tych układów logicznych znajdującego się sumatorem 70. Dla operacji typu ADD, po której następuje operacja typu ADD, trzy argumenty są kierowane do wejść 70A, 70B, 70C sumatora 70 i wyjście 70D sumatora 70 jest podawane na wyjściu AO jednostki arytmetycznologicznej 65. Działanie jednostki arytmetyczno-logicznej 65 w celu wykonania drugiej instrukcji i zawartej w drugiej tabeli pamięci 54, gdzie nie ma zależności danych pmiędzy pierwszą i drugą instrukcją, jest proste. W tym przypadku, jedynie dwa argumenty są podawane do jednostki arytmetyczno-logicznej 65. Dlatego, jeżeli druga instrukcja jest instrukcją dodawania, dwa argumenty będą podawane do sumatora 70, razem z zerem na miejscu trzeciego argumentu, przy czym wyjście sumatora 70Uzst wybierane przez wyjściowy multipekser 95 jako wyjścieUednostki arytmetyczno-logicrnzU 65. Jeżeli druga instrukcja jest instrukcją logiczną, operacja logiczna może być wykonana przez skierowanie dwóch argumentów do pierwszych układów logicznych 71, 72 i 73, wybranie odpowiedniego wyjścia, i następnie przesłanie wyniku przez sumator 70 przez dodanie zer do innych dwóch wejść sumatora 70. W tym przypadku, sygnał na wyjściu 70D sumatora 70 byłby równy wynikowi logicznemu i byłby wybrany przez wyjściowy multiplekser 95 jako wyjście AO jednostki arytmetyczno-logicznej 65. Alternatywnie, jeden argument może być przeprowadzony przez sumator 70 przez dodanie dwóch zer, czego wynikiem będzie podanie tego argumentu jako sygnału na wyjściu 70D sumatora 70. Ten argument zostaje połączony z innym argumentem w drugich układach logicznych 90, 92 i 93, przy czym wyjście właściwego układu logicznego jest wybrane przez wyjściowy multiplekser 95 jako wyjście AO jednostki arytmetyczno-logicznej 65.

Gdy instrukcje są składane, jak pokazano to na fig.8, instrukcja zawarta w pierwszej tabeli pamięci 52 rejestru 50 będzie dekodowana w układzie logicznym 40, wybierane będą jej argumenty przez układ przełączający 42 a wykonanie wybranej operacji na wybranych argumentach nastąpi w jednostce arytmetyczo-logicznej 45. Ponieważ jednostka arytmetyczno-logiczna 45 jest przewidziana do wykonywania instrukcji pojedynczej, dane są dwa argumenty z wybranego rejestru poprzez wejście AI0 i ALI, przy czym wskazany wynik jest dany na wyjściu 47.

Z tego względu, w przypadku konfiguracji przedstawionej na fig.8, jednostka arytmetyczno-logiczna 65 zmniejszająca zalezność danych, w połączeniu z konwencjonalną jednostką

165 457 arytmetyczno-logiczną45, realizuje współbieżne (lub równoległe) wykonywanie dwu instrukcji, nawet gdy istnieje zależność danych pomiędzy instrukcjami.

Generacja adresów może także być poddana wpływowi zatorów danych, które będą określane jako zatory adresów AHAZ. Poniższa sekwencja przedstawia złożoną sekwencję instrukcji Systemu/370, która jest wolna od zatorów adresowych:

AR R1, R2

S R3, D(R4, R5), gdzie D reprezentuje przesunięcie o trzy półbajty. Nie występują tu AHAZ, ponieważ R4 i R5, które są stosowane w obliczeniu adresu, nie były zmienione przez poprzednią instrukcję. Zatory adresowe istnieją w poniższych sekwencjach:

ARR1, R2

SR3, D(R1,R5)

Ar R1, R2

S R3, D(R4, R1)

Powyższe sekwencje demonstrują łączenie instrukcji RR (kategoria 1 na fig.5) z instrukcjami RX (kategoria 9) przedstawiające AHAZ. Inne kombinacje zawierają instrukcje RR złożone z instrukcjami RS i SI.

Dlajednostki arytmetyczno-logicznej elimującej blokady, należy utworzyć nowe operacje wynikające z eliminacji blokad AHAZ na drodze analizy wszystkich kombinacji sekwencji instrukcji i konfliktów argumentów adresów. Analiza wskazuje, że pospolite blokady, takie jak zawarte w powyższych sekwencjach instrukcji, mogą być wyeliminowane przy pomocy jednostki arytmetyczno-logicznej typu cztery do jednego.

Funkcje, które musiałyby być realizowane przez jednostkę arytmetyczno-logiczną do eliminowania wszystkich blokad AHAZ dla architektury na poziomie instrukcji Systemu/370 są wymienione na fig.10.Dla tych przypadków, gdzie cztery wejścia nie są wyszczególnione, należy podać w sposób niejawny zero. Schemat logiczny jednostki arytmetyczno-logicznej eliminującej blokady AHAZ, określone przez funkcje z fig. 10, jest podany na figurze 11. Duży podzbiór funkcji określonych na fig. 10, ale nie wszystkie, jest realizowany przez przedstawioną jednostkę arytmetyczno-logiczną. Podzbiór ten składa się z funkcji danych w rzędach od 1do 21 na fig. 10. Decyzja do tego, którą funkcję należy uwzględnić jest decyzją realizacyjną.

Jak pokazano na fig. 11, przedstawiona jednostka arytmetyczno-logiczna zawiera sumator 100, w którym dwa trójwejściowe, dwuwyjściowe sumatory 101 i 102 z zachowaniem przeniesienia są połączone kaskadowo w dwuwejściowy, jednowyjściowy sumator równoległy 103, w taki sposób, że sumator 100 jest w efekcie czteroargumentowym, jednowynikowym sumatorem niezbędnym do działania jednostki arytmetyczno-logicznej na fig.l 1.

Na fig. 10 przedstawiono uproszczoną, kosztem logiki sterującej, strukturę jednostki arytmetyczno-logicznej. Najlepiej wyjaśni to przykład. Rozważmy dwie następujące sekwencje instrukcji Systemu/370.

NR R1, R2 (4)

SR3,D(R1,R5) i

NRR1, R2 (5)

SR3, D(R4, R1)

Niech ogólna notacja dla tej sekwencji będzie:

NR rl, r2

S r3, D(R4, R5).

Dla pierwszej sekwencji, adres argumentu jest:

OA = D + (R1 A R2) + 5 podczas gdy dla drugiej sekwencji jest:

OA = D + R4 + (R1 A R2)

Dla uproszczenia sterowania wykonaniem,,kosztem złożoności jednostki arytmetycznologicznej, poniższe dwie operacje musiałyby być wykonywane przez jednostkę arytmetycznologiczną:

OA = AG10 + (AGI 1 A AG12) + AG13

OA = AG10 + AG12 (AG11 A AG13)

165 457 z której D jest podawane do AGIO, r2 jest podawane do AGI1, r4 jest podawane do AGI2 i r5 jest podawane do AGI3. Jednostka arytmetyczno-logiczna mogłaby być uproszczona, jeżeli układ sterujący wykrywa, który z r4 do r5 blokuje się z rl i dynamicznie kieruje ten rejestr do AGI2. Inny rejestr byłby podawany do AGI3. Dla podtrzymania tego założenia, jednostka arytmetyczno-logiczna musi jedynie realizować operację:

OA = AGIO + (AG11 A AG12 + AG13

Kompromisy, takie jak powyższe, są czynione celem zmniejszenia złożoności jednostki arytmetyczno-logicznej generacji adresów jak również wykonania i określenia odgałęzienia jednostki arytmetyczno-logicznej.

Jednostka arytmetyczno-logiczna z fig. 11 może być zastąpiona przez jednostkę arytmetyczno-logiczną 65 z fig.8. W tym przypadku układ logiczny 60 dekodujący i sterujący odzwierciedlałby odpowiednio funkcje z fig. 10.

Należy wykonać podobne analizy jak dla jednostki arytmetyczno-logicznej eliminującej blokady, aby otrzymać wpływ łączenia na jednostkę arytmetyczno-logiczną określającą rozgałęzienia, pokazaną na figurach 12 i 13. Ta jednostka arytmetyczno-logiczna określająca rozgałęzienia pokrywa funkcje wymagane przez instrukcje porównując wartości rejestrów. Są to instrukcje rozgałęzienia BXLE, BXH, BCT i BOTR, w których wartość rejestru jest zwiększana o zawartość drugiego rejestru (BXLE i BXH) lub jest zmniejszana o jeden (BCT i BCTR) przed porównaniem z wartością rejestru (BXLE i BXH) lub O (BCT i BCTR) celem określenia wyniku rozgałęzienia. Rozgałęzienia warunkowe nie są wykonywane przez tę jednostkę arytmetycznologiczną.

Jednostka arytmetyczno-logiczna przedstawiona na fig. 13 zawiera wielostopniowy sumator 110, w którym dwa sumatory 111 i 112 z zachowaniem przeniesienia są połączone kaskadowo, przy czym dwa wyjścia sumatora 112 z zachowaniem przeniesienia dają dwa wejścia dla sumatora równoległego 113. To połączenie tworzy w efekcie sumator czterowejściowy, o pojedynczym wyniku dla jednostki arytmetyczno-logicznej z fig. 13.

Jako przykład zatorów danych, które mogą wystąpić, rozważmy następującą sekwencję instrukcji:

AL R1, D(R2, R3)

BCT R1, D(R2, R3)

Niech (x) oznacza zawartość komórki pamięci x. Wyniki wykonania są następujące:

R1 = R1 + [D + R2 + R3] - 1

Rozgałęzienie, jeżeli (R1 + [D + R2 + R3]) -1=0

Porównanie to mogłoby być wykonane przez wykonanie operacji:

R1 + [D + R2 + R3] - 1- 0

Wyniki analizy dla jednostki arytmetyczno-logicznej określającej rozgałęzienia są podane na fig. 12 i 13 bez dalszego omówienia. Funkcje realizowane przez ten układ logiczny są to funkcje określone przez rzędy 1 do 25 na fig. 12.

Jednostka arytmetyczno-logiczna z fig. 13 może być zastąpiona przez jednostkę arytmetyczno-logiczną 65 z fig.8. W tym przypadku, układ logiczny 60 dekodowania i sterowania odzwierciedlałby odpowiednio funkcje z fig. 12.

Niektóre funkcje, które wynikają z konfliktów argumentów są bardziej skomplikowane niż inne. Na przykład, sekwencja instrukcji:

AR R1, R2

AR R1, R1 wymaga dla eliminacji blokady danych jednostki arytmetyczno-logicznej typu cztery do jednego, razem z towarzyszącą jej złożonością, ponieważ jej wykonanie daje wynik:

R1 =(R^1 +R2) + (R1 +R2)

165 457

Wynikiem inych sekwencji są operacje, które wymagają włączenia dodatkowego opóźnienia do jednostki arytmetyczno-logicznej celem wyeliminowania blokady. Sekwencją przedstawiającą zwiększone opóźnienie jest:

SR R1, R2

LPR R1, R2 której wynikiem jest operacja

R1 = (R1 - R2)

Ta operacja nie nadaje się do równoległego wykonywania, ponieważ wyniki odejmowania są niezbędne do przygotowania wykonania wartości bezwzględnej.

Zamiast eliminacji wszytkich blokad w jednostce arytmetyczno-logicznej, może być dana logika podająca instrukcja lub preprocesor przeznaczony do wykrywania sekwencji instrukcji, które prowadzą do bardziej skomplikowanych funkcji. Detekcja przy pomocy preprocesora powoduje uniknięcie opóźnienia wyjścia logiki, które stanowi często ścieżkę krytyczną. Gdy taka sekwencja zostaje wykryta, logika wyprowadzająca lub preprocesor będą odwracać celem podania sekwencji w modzie skalarnym, unikając konieczności eliminacji blokady. Decyzja, która sekwencja instrukcji powinna lub nie powinna eliminować ich blokady, jest decyzją realizacyjną zależną od czynników znajdujących się poza przedmiotem tego wynalazku. Mimo to, należy zauważyć związek pomiędzy złożonością realizacyjną jednostki arytmetyczno-logicznej a złożonością logiki wydającej.

Zatory generacji adresów będą także dawać przyczynę do kompromisów w realizacji wynalazku. Na przykład, większość blokad generacji adresów może być wyeliminowana przy zastosowaniu jednostki arytmetyczno-logicznej typu cztery do jednego.

Poniższa sekwencja:

AR R1, R2

SR3, D(R1, R1):

nie pasuje jednakże do tej kategorii. Dla tego przypadku wymagana jest jednostka arytmetyczno-logiczna typu pięć do jednego do eliminacji blokady AHAZ, ponieważ wynikowa operacja jest:

OA = D + (R1 + R2) + (R1 + R2) gdzie OA jest wynikowym adresem argumentu. Jak poprzednio, zawarcie tej funkcji w jednostce arytmetyczno-logicznej jest dycyzją realizacyjną, która zależy od częstotliwości występowania takiej blokady. Podobne wyniki stosują się do jednostki arytmetyczno-logicznej określającej rozgałęzienie.

Można wykonać analizy podobne do przedstawionych powyżej celem uzyskania sprzętu eliminującego blokady dla większości ogólnych przypadków n blokad. Dla przeprowadzenia tej analizy należy odnieść się do figury 14. Zakładając proste blokady danych takie jak:

AR R1, R2

AR R3, R1, w którym zmieniany rejestr z pierwszej instrukcji jest stosowany jako tylko jeden z argumentów drugiej instrukcji, do eliminacji blokady byłaby potrzebna jednostka arytmetyczno-logiczna typu (n+1) do jednego. Na przykład, do eliminacji trzech blokad przy powyższym założeniu, potrzebna byłaby jedna jednostka arytmetyczno-logiczna typu cztery do jednego. Wymagałoby to też zastosowania dodatkowego stopnia sumatora ochrony przeniesienia w jednostce arytmetyczno-logicznej. Wzrost liczby stopni takiego sumatora wymaganych w jednostce arytmetyczno-logicznej nie jest jednakże liniowy. Jednostka arytmetyczno-logiczna zaprojektowana do operowania dziewięcioma argumentami jako pojedyncza jednostka wykonawcza posiadałaby cztery stopnie sumatora ochrony przeniesienia i jeden stopień sumatora równoległego. Można to stwierdzić na podstawie fig. 14, w której każda pionowa linia reprezentuje wejście sumatora i każda pozioma wskazuje sumator. Sumatory ochrony przeniesienia są przedstawione przez linie poziome 1000-1060, podczas gdy sumator równoległy jest przedstawiony linią 1090. Każdy sumator ochrony przeniesienia ma dwa wyjścia z trzech wejść. Redukcja strumieni wejściowych trwa od stopnia do stopnia aż do chwili, gdy ostatni sumator

165 457 ochrony przeniesienia zmniejszy liczbę strumieni do dwóch. Następny sumator jest sumatorem równoległym i ma jedno wyjście końcowe z dwóch wejść. Zakładając jedynie operacje arytmetyczne, jednostopniowy sumator równoległy i czterostopniowy sumator ochrony przeniesienia, może być zrealizowane wykonanie dziewięciu argumentów jako pojedynczej jednostki przy zastosowaniu proponowanego układu.

Blokady danych pogarszają wydajność uzyskaną w komputerach z przetwarzaniem potokowym przez wprowadzenie zatorów do potoku. Niektóre z tych blokad mogą być usunięte przez przemieszczanie kodu i planowanie instrukcji. Inną propozycją zmniejszenia obniżenia wydajności jest zdefiniowanie instrukcji, które obsługują blokady danych. Słabym punktem tej propozycji jest ograniczenie liczby blokad, które mogą być obsługiwane przy sensownej wielkości instrukcji. Ponadto, rozwiązanie to nie jest dostępne w przypadku komputerów zgodnych z architekturą System/370. Zgodnie z wynalazkiem zostało zaprezentowane alternatywne rozwiązanie dla usunięcia blokad instrukcji.

Wynalazek oferuje korzyści polegające na braku żądania zmian architektury, braku żądania wbudowania wszystkich możliwych par instrukcji i ich blokad do zbioru instrukcji, wykazuje jedynie niewielki lub żaden wpływ na czas cyklu maszyny, wymaga mniejszej ilości sprzętu i jest zgodny z komputerami Systemu/370.

R1 R2 -R3

Y >	z y
r10A	Λ0Β .

FIG. 3

WYNIK = IR1)ł(R2)-(R3l

I

AO

FIG .9

165 457

1. INSTR. ŁADÓW.LOGICZNE, ARYTMET .PORÓWNYWANIA W FORMACIE RR . LCR - ŁADUJ DOPEŁNIENIE . LPR - ŁADUJ Z PLUSEM . LNR - ŁADUJ Z MINUSEM . LR - ŁADUJ REJESTR . LTR - ŁADUJ I SPRAWDŹ . NR - I . OR - LUB . XR - ALBO . AR - DODAJ . SR - ODE JM IJ . ALR - DODAJ LOGICZNIE . SLR - ODEJMIJ LOGICZNIE . CLR - PORÓWNAJ LOGICZNIE . CR - PORÓWNAJ

2. INSTRUKCJE PRZESUNIĘĆ W FORMACIE RS (BEZ DOSTĘPU DO PAMIĘCI) . SRL - PRZESUŃ W PRAWO LOGICZNIE ‘ * . SLL - PRZESUŃ W LEWO LOGICZNIE . SRA - PRZESUŃ W PRAWO ARYTMETYCZNIE . SLA - PRZESUŃ W LEWO ARYTMETYCZNIE . SRDL- PRZESUŃ W PRAWO LOGICZNIE . SLDL - PRZESUŃ W LEWO LOGICZNIE . SRDA - PRZESUŃ W PRAWO ARYTMETYCZNIE . SLDA - PRZESUŃ W LEWO ARYTMETYCZNIE

3. ROZGAŁĘZIENIA-W ZALEŻNOŚCI OD LICZNIKA INDEKSU . BCT - ROZGAŁĘZIENIE W ZALEŻNOŚCI OD ZLICZENIA (FORMAT RX) . BCTR - ROZGAŁĘZIENIE W ZALEŻNOŚCI OD ZLICZENIA (FORMAT RR) . ΒΧΗ - ROZGAŁĘŹ.W ZALEŻN OD INDEK. W WYS. POZ.(FORMAT RS)

- BXLE- ROZGAŁĘŹ.W ZALEŻN. OD INDEK. W NISK. POZ.(FORMAT RS)

4. ROZGAŁĘZIENIA-W ZALEŻNOŚCI OD WARUNKU . BC - ROZGAŁĘZIENIE W ZALEŻNOŚCI OD WARUNKU (FORMAT RX) . BCR - ROZGAŁĘZIENIE W ZALEŻNOŚCI OD WARUNKU (FORMAT RR)

5. ROZGAŁĘZIENIA-I DOŁĄCZENIA . BAL - WYKONAJ ROZGAŁĘZIENIE I DOŁĄCZ (FORMAT RX) . BALR-WYKONAJ ROZGAŁĘZIENIE I DOŁĄCZ (FORMAT RR) . BAS - WYKONAJ ROZGAŁĘZIENIE I ZAPISZ (FORMAT RX ) . BASR-WYKONAJ ROZGAŁĘZIENIE I ZAPISZ (FORMAT RR)

FIG. 4A

165 457

6. ZAPISY DO PAMIĘCI . STCM -ZAPISZ DO FAM. ZNAKI POD MASKA (ZAR 0-4 BAJTY,FORMAT RS) . MVI - PRZEŚLIJ W TRYBIE BEZPOŚREDNIM (JEDEN BAJT, FORMAT SI, . ST - ZAPISZ OO PAMIĘCI (4 BAJTY) . STC - ZAPISZ DO PAMIĘCI ZNAK (JEDEN BAJT, . STH-ZAPISZ DO PAMIĘCI POLOWE (2 BAJTY)

7. OPERACJE ŁADOWANIA . LH - ZAŁADUJ POLOWKĘ (2 BAJTY, . L - ZAŁADUJ (4 BAJTY,

8. LA - ZAŁADUJ ADRES

9. INSTR. LOGICZNE, ARYTMET., LOG., WSTAW , PORÓWNYW W FOR. RX/SI/RS . A - DODAJ . AH - DODAJ POŁÓWKĘ . AL - DODAJ LOGICZNIE . N - I . O - LUB . S - ODEJMIJ . SH - ODEJMIJ POŁÓWKĘ . SL - ODEJMIJ LOGICZNIE . X - ALBO . IC - USTAW ZNAK . ICM -WSTAW ZNAKI POD MASKĄ (ZAŁADOWANIE 0 DO 3 BAJTÓW, . C - PORÓWNAJ . CH - PORÓWNAJ POŁÓWKĘ . CL - PORÓWNAJ LOGICZNIE .

. CLI - PORÓWNAJ LOGICZNIE W TRYBIE BEZPOŚREDNIM . CLM- PORÓWNAJ ZNAK LOGICZNIE POD MASKĄ

10. TM-SPRAWDŹ PRZEZ MASKĘ

FIG. 4B

165 457

FUNKCJE POWSTAJĄCE PRZEZ ŁĄCZENIE INSTRUKCJI ' LOGICAL (¢) , ΑΟΟ(ς)
SEKWENCJA	STAN BLOKADY	FUNKCJA
LOGICAL.ADD	R1=R3*R2XR4	(RlpR2)£R4
LOGI CAL,ADD	R1=R4*R2*R3	R3«RlęsR2)
LOGICAL.ADD	R1=R2=R3*R4	(RlęjRl)fR4
LOGICAL.ADD	R1=R2=R4^R3	R3f( RlęJRl)
LOGICAL.ADD	R1=R3=R4*R2	(RW)f(Rlę>R2:
LOGICAL.ADD	R1=R2=R3=R4	(Rlę?Rl)f( RlęPRf
ADD.LOGICAL	R1=R3*R2*R4	(Rl{R2)pR4
ADD.LOGICAL	Rl=R4#R2s*R3	R3ęi(RlfR2)
ADD.LOGICAL	R1=R2=R3*R4	(Rl{-Rl)j»R4
ADD, LOGICAL	R1=R2=R4#R3	R^RlfRl)
ADD, LOGICAL	R1=R3=R4^R2	(RlfR2)9>(RlfR2;
ADD, LOGICAL	R1=R2=R3=R4	(RlfRl)ęo(RlfRr
LOGICAL, LOGICAL	R1=R3^^R4	(Rl$ffR2)ę>R4
LOGICAL, LOGICAL	Rl=H4*«2ytR3	R3?(Rlę*2)
LOGICAL, LOGICAL	R1=R2=R3*R4	(RlęoRl)ęJR4
LOGICAL .LOGICAL	R1=R2=R4#R3	R3y<Rlę»Rl)
LOGICAL. LOGICAL	R1=R3=R4*R2	(Rlę>R2)ęe<Rlę»R2;
LOGIC AL, LOGICAL	R1=R2=R3=R4	(Rl<pRl)<-(Rtę»Rf
ADO,ADD	Rl=R3?tft2?!R4	(RlfR2)fR4
ADD.ADD	R1=R4^R2^R3	R3«RlfR2)
ADD.ADD	R1=R2=R3#R4	(RlfRl)fR4
ADD.ADO	R1-R2=R3*R3	R3f(RlfRl)
ADD.ADD	R1=R3=R4*R2	(RlfR2)<(RtfR2;
ADD,ADD	R1=R2=R3=R4	(RlfRl)f(RlfRi;

FIG. 5

165 457

FUNKCJE WYMAGAJĄCE implementacji dla eliminacji blokad ZWIĄZANYCH Z ZATORAMI DANYCH
RZĄD	FUNKCJA	OPl	0P2
1	AI2
2	-AI2
3	/AI2/
4	-/AI2/
5	Ali OPl AI2	A,V,©,+.-
6	Ali OPl (-AI2)	A,V,®
7	Ali OPl /AI2/	A.V,®
8	Ali OPl (-/AI2/)	A.V,®
9	(-AI2) OPl (-AI2)	A,V.®
10	/AI2/ OPl /AI2/	A,V.®
11	(-/AI2/> OPl (-/AI2/)	A.V.®
12	AIO OPl AI2
13	/AIO/ OPl AI2	+,-
14	(-/AIO/) OPl A12
15	(—AIO) OPl AI2
16	/AIO/ OPl /AI2/	+,-
17	(-/AIO/) OPl /AI2/	+(-
18	AI2 OPl AI2	A,V,®
19	-( AI2 OPl AIO)	A.V.®
20	AI2 OPl AIO	A,V.®
21	/AI2 OPl AIO/	A,V,®
22	-/AI2 OPl AIO/	A.V.®
23	Ali 0P2 (AI2 OPl AIO)	+ *	+ -
24	-Ali 0P2 (AI2 OPl AIO)	+ »	+
25	(AI2 OPl AIO) 0P2 Ali	A,V,®	A.V. ©,+,-
26	(AI2 OPl AIO) 0P2 Ali	+.-	A,V,®
27	-(AI2 OPl AIO) 0P2 Ali	A.V.®	+
28	AI2- 1
29	(-AI2)- 1

FIG. 6A

165 457

30	/AI2/ - 1
31	(-/AI2/) - 1
32	(AI2 0P1 AIO) - 1	A,V,©,+,-
33	(AI2 - 1) 0P1 Ali	A.V.®
34	AI2 0P1 (AIO - 1)	+ »
35	(AIO - 1) 0P1 AI2	+ -
36	-<AI2 - 1)
37	(AI2 - 1) 0P1 (AI2 - 1)	A,V,®
38	/AI2 - 1/
39	-/AI2 - 1/
40	/AI2 0P1 AIO/	+,-
41	-/AI2 0P1 AIO/	+
42	(AI2 0P1 AIO) 0P2 (AI2 0P1 AIO)	Λ.ν,Φ	Λ,ν. ©,+.-
43	(AI2 0P1 AIO) 0P2 (AI2 0P1 AIO)	+.-	Λ.ν,Φ
44	AIO + Ali + AI2 + AI3
45	-AIO + Ali - AI2 + AI3
46	(AI2 - 1) 0P1 (AI2 - 1)	+ *

FIG. 6B

165 457

DROGI PRZESYŁANIA ARGUMENTÓW DLA WYTWORZENIA WYMAGANYCH 0	PERACJI DLA INSTR.TYPU LOGICAL-ADD
WYMAGANE OP	ALU OP	OPl	0P2	AIO	Ali	AI2
(RlępR2)ĆR4	(AI2 OP1 AIO) 0P2 Ali	A,V,®	+.-	R2	R4	R1
R3<TRlęoR2)	(AI2 OPl AIO) 0P2 Ali	A.V,®	+	R2	R3	R1
	-(AI2 OP1 AIO) OP2 Ali	A.V,®	+	R2	R3	R1
(Rl?Rl)fR4	(AI2 OP1 AIO) 0P2 Ali	A,V,®	+ »	R2(=R1)	R4	R1
R3f(Rl?>Rl)	(AI2 OP1 AIO) 0P2 Ali	A,V.®	+	R2(=R1)	R3	R1
	-(AI2 OPl AIO) 0P2 Ali	A.V.®	+	R2(=R1)	R3	R1
(RlęrfR2)<f(RlęoR2)	(AI2 OPl AIO) 0P2 (AI2 OPl AIO)	A.V.®
(RlfR2)<pR4	(AI2 OPl AIO) 0P2 AI3	+ - 1	A,V,®	R2	R4	R1
R3p(Rl<R2)	(AI2 OPl AIO) 0P2 Ali	+ »	A.V.®	R2	R3	R1
(Rl<Rl)ęjR4	(AI2 OPl AIO) 0P2 Ali	+ - »	A.V,®	R2(=R1)	R4	R1
R3ę^Rl^Rl)	(AI2 OPl AIO) OP2 Ali	+ - (	A.V.®	R2(=R1)	R3	R1
(RlfR2)ęp(Rl<R2)	(AI2 OPl AIO) 0P2 (AI2 OPl AIO)	+ »	A.V,®
(RlpR2)?R4	(AI2 OPl AIO) OP2 Ali	A.V.®	A.V.®	R2	R4	R1
R3?<R1W2)	(AI2 OPl AIO) 0P2 Ali	A,V.®	A,V,®	R2	R3	R1
(RlpRl)iPR4	(AI2 OPl AIO) 0P2 Ali	A.V.®	A,V,®	R2( =R1)	R4	R1
R3ę<Rlęi>Rl)	(AI2 OPl AIO) 0P2 Ali	A.V.®	A.V,®	R2( =R1)	R3	R1
(Rl^R2)^(RliSR2)	(AI2 OPl AIO) 0P2 (AI2 OPl AIO)	A.V,®	A.V.®
(Rl£R2)fR4	Ali 0P2 (AI2 OPl AIO)	+ 1	+	R2	R4	R1
	-Ali 0P2 (AI2 OPl AIO)		+	R2	R4	R1
R3«R1<R2)	Ali 0P2 (AI2 OPl AIO)			R2	R3	R1

FIG. 7A

(R1(R1)ĆR4	Ali 0P2 (AI2 OPl AIO)	+, -	+	R2(=R1)	R4	R1
	-Ali 0P2 (AI2 OPl AIO)	+. -	+	R2(=R1)	R4	R1
R3(RlfRl)	Ali 0P2 (AI2 OPl AIO)	+. -	+. -	R2(=R1)	R3	R1
(RlfR2)f(RlfR2)	AI2 OPl AIO + Ali OP2 AI3	+, -	+, -
UWAGA: TE OPERACJE, KTÓRE WYSTĘPUJĄ , GDY SPECYFIKACJE REJESTRÓW DLA R1,R3i R4 SĄ TAKIE SAME, NIE ZOSTAŁY ZAIMPLEMENTOWANE W LOGICZNYM PRZEPŁYWIE DANYCH Z FIG.10 ZATEM DROGI ICH ARGUMENTÓW NIE ZOSTAŁY UMIESZCZONE

FIG. 7B

165 457

STRUMIEŃ INSTRUKCJI ZAWIERAJĄCY INSTUKCJE ZŁOŻONE '

FUNKCJE WYMAGAJĄCE IMPLEMENTACJI DLA ELIMINACJI BLOKAO AHAZ
RZĄD	FUNKCJA	0P1
1	AGI2
2	-AG 12
3	/AG12/
4	-/AG12/
5	AGI1 0P1 AGI2	A.V.®,+,-
6	AGIO + AGI2
7	AGIO - AGI2
8	AGIO + AGI2 + AGI3
9	AGIO - AGI2 + AGI3
10	AGIO + AGI2 - AGI3
11	AGIO - AGI2 - AGI3
12	AGIO + /AGI2/
13	AGIO - /AGI2/
14	AGIO + /AGI2/ + AGI3
15	AGIO + AGI2 + /AGI3/
16	AGIO + /AGI2/ + /AGI3/
17	AGIO - /AGI2/ + AGI3
18	AGIO + AGI2 - /AGI3/
19	AGIO - /AGI2/ - /AGI3/
20	AGIO + (AGI1 0P1 AGI2)	A,V,®,+.-
21	AGIO + (AGH 0P1 AGI2) + AGI3	A,V,©,+,-
22	AGIO + (AGH 0P1 AGI2) + (AGI3 0P1 AGH)	A,V,®.+.-

FIG. 10

165 457

BDIO BDI1 B0I2 BDI3

AGO

FIG. 11

165 457

FUNKCJE WYMAGAJĄCE IMPLEMENTACJI DLA ELIMINACJI BLOKAD AHAZ
RZĄD	FUNKCJA	0P1
1	BDI1 + BDI2 - BDI3
2	BDI1 + B0I2 + BDI3
3	B0I1 + BDI2 + /BDI3/
4	BDI1 + BDI2 - /BDI3/
5	BDI1 - BDI2 - BDI3
6	BDI1 + /BDI2/ - BDI3
7	BDI1 - /BDI2/ - BDI3
8	(-BDIO) + BDI2 - BDI3
9	(-BDIO) - BDI2 - BDI3
10	(-BDIO) + BDI2 + BDI3
11	BDIO + BDI2 - BDI3
12	/BDIO/ + BDI2 - BDI3
13	/BDIO/ + BDI2 - /BDI3/
14	(-/BDIO/) + BDI2 - BDI3
15	(-/BDIO/) + BDI2 + /BDI3/
16	(-/BDIO/) - /BDI2/ - BDI3
17	/BDIO/ + /BDI2/ - BDI3
18	(BDIO 0P1 BDI3) + BDI1 - BDI2
19	BDI1 + BDI2 - (BDI3 0P1 BDIO)	A,V,®,+,-
20	BDI1 - BDI2 + (BDI3 0P1 BDIO)	A,v,®,+ -
21	BDI3 - 1 - 0
22	(-BDI3) - 1 - 0
23	/BDI3/ - 1 - 0
24	(-/BDI3/) - 1 - 0
25	(BDI3 0P1 BDIO) - 1 - 0	A.V,®.+,-
26	(BDI3 0P1 BDIO) + BDI2 - (BDI3 0P1 BDIO)	A,V,©,+,~
27	(BDI3 0P1 BDIO) - BDI2 + (BDI3 0P1 BDIO)	Λ.ν.ΦΛ-

FIG. 12

165 457

Departament Wydawnictw UP RP. Nakład 90 egz. Cena 1,00 zł.

Claims (11)

1. Zastrzeżenia patentowe

   1. Układ eliminacji zależności danych przetwarzanych w komputerze, zwłaszcza w komputerze o architekturze pozwalającej na szeregowe wykonywanie sekwencji operacji skalarnych, zawierający jednostkę arytmetyczno-logiczną, znamienny tym, że zawiera rejestr rozkazów (50) z co najmniej dwiema tablicami pamięci (52,54), co najmniej trzy rejestry uniwersalne (63), każdy dla jednego argumentu operacji, układ przełączający (64), który jest dołączony do wspólnego wyjściarejestrów uniwersalnych (63), układ logiczny (60) dekodowania i sterowania, którego wejścia są dołączone do wyjść rejestru rozkazów (50), wyjście (62) wyboru rejestru jest dołączone do układu przełączającego (64), a wyjście (66) wyboru funkcji dołączone do jednostki arytmetyczno-logicznej (65), przy czym jednostka arytmetyczno-logiczna (65) ma trzy wejścia (AI0, AI1, AI2) argumentów operacji dołączone do układu przełączającego (64) oraz ma wyjście (A0).
2. 2. Układ według zastrz. 1, znamienny tym, że jednostka arytmetyczno-logiczna (65) zawiera sumator (70), którego trzy wejścia (70A, 70B, 70C) argumentu operacji są dołączone do wejść (AI0 AI1, AI2) argumentów operacji tej jednostki, aż jedno wyjście (70D) wyniku jest dołączone do wyjścia (A0) tej jednostki.
3. 3. Układ według zastrz. 2, znamienny tym, że sumator (70) zawiera sumator ochrony przeniesienia (10), którego trzy wejścia (10A, 10B, 10C) są dołączone do wejść (70A, 70B, 70C) argumentów operacji sumatora (70), oraz sumator równoległy (22), którego jedno wejście jest dołączone do wyjścia (14) sumy a drugie do wyjścia (12) przeniesienia sumatora ochrony przeniesienia (10), przy czym jedno wyjście (26) sumatora równoległego (22) jest dołączone do wyjścia (70D) wyniku sumatora (70).
4. 4. Układ według zastrz. 2, znamienny tym, że dwa z trzech wejść (AI0, AI1, AI2) argumentów operacji jednostki arytmetyczno-logicznej (65) są dołączone do trzech pierwszych układów logicznych (71, 72, 73), które to układy są następnie dołączone do jednego (70C) z trzech wejść (70A, 70B, 70C) argumentów operacji sumatora (70).
5. 5. Układ według zastrz. 4, znamienny tym, że pierwszy (71) z trzech pierwzych układów logicznych (71, 72, 73) jest elementem I, drugi (72) jest elementem LUB zaś trzeci (73) jest elementem ALBO.
6. 6. Układ według zastrz. 2, znamienny tym, że jedno z trzech wejść (AI0, AI1, A12) argumentów operacji jednostki arytmetyczno-logicznej (65) i wyjście (70D) wyniku sumatora (70) są dołączone do trzech drugich układów logicznych (90,92,93), które to układy są następnie dołączone do wyjścia (A0) jednostki arytmetyczno-logicznej (65).
7. 7. Układ według zastrz. 6, znamienny tym, że pierwszy (90) z trzech drugich układów logicznych (90, 92, 93) jest elementem I, drugi (92) jest elementem LUB zaś trzeci (93) jest elementem ALBO.
8. 8. Układ według zastrz. 4, znamienny tym, że dwa (AI0, AI1) z trzech wejść (AI0, AI1, AI2) argumentów operacji jednostki arytmetyczno-logicznej (65) są dołączone do pierwszego multipleksera (80), który jest następnie dołączony do trzech pierwszych układów logicznych (71,72,73).
9. 9. Układ według zastrz. 4, znamienny tym, że trzy pierwsze układy logiczne (71,72,73) są dołączone do drugiego multipleksera (75), który jest następnie dołączony do jednego (70C) z trzech wejść (70A, 70B, 70C) argumentów operacji sumatora (70).
10. 10. Układ według zastrz. 6, znamienny tym, że trzy drugie układy logiczne (90, 92, 93) są dołączone do wyjściowego multipleksera (95), który jest następnie dołączony do wyjścia (A0) jednostki arytmetyczno-logicznej (65).

    165 457
11. 11. Układ wedhig zastrz. 1, znamienny tym, układ przełączający zawie rei multiplekser przekazujący eemertość rejestrom uniwersalnych (63) do treech wejść (A10, AI1, AI2) ergpmentóm operacji jednostki arytmetyczno-logicznej (65).