Omega желісі: параллельді есептеулерде қолданылатын, көп сатылы конфигурация. Байланыс үшін "толық шайқау" алгоритмі мен кезеңдік коммутаторлар пайдаланады.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Желі конфигурациясының түрі
Form of network configuration
Омега желісі – параллельді есептеу архитектураларында жиі қолданылатын желі конфигурациясы. Бұл тікелей емес топология, ол толық араласу (perfect shuffle) өзара байланыс алгоритміне негізделген.
An Omega network is a network configuration often used in parallel computing architectures. It is an indirect topology that relies on the perfect shuffle interconnection algorithm.
Қосылым архитектурасы
8x8 Omega желісі – көп сатылы өзара байланыс желісі, яғни өңдеу элементтері (ПЭ) бірнеше сатылы коммутаторлар арқылы қосылады. Кірістер мен шығыстар суретте көрсетілгендей адрестеледі. Әр сатыдан шыққан шығыстар келесі сатының кірістерімен толық араластыру жүйесі арқылы байланысады. Бұл, әр сатыдағы байланыстар екі тең бөлікке бөлінген және содан кейін біріктірілген карталар жинағының қозғалысын білдіреді, мұнда әр карта бір жинақтан екінші жинақтың сәйкес картасымен кезектесіп орналасады. ПЭ-дің екілік өрнегі тұрғысынан қарағанда, толық араластырудың әр сатысы циклдық логикалық солға жылғаю ретінде қарастырылуы мүмкін; адрестегі әр бит бір рет солға жылғады, ең маңызды бит ең кіші маңызды битке көшеді. Әр сатыда, кірістердің жақын жұптары қарапайым алмастыру элементіне қосылады, оны тура (кірістерді тікелей шығыстарға жіберу) немесе қиылысқан (жоғарғы кірісті төменгі шығысқа және керісінше жіберу) күйге келтіруге болады. N өңдеу элементі үшін Omega желісі әр сатыда N/2 коммутаторды және log2N сатыдан тұрады. Бұл коммутаторлардың орналасуы желіде кез келген уақытта қол жетімді қосылу жолдарын анықтайды. Мұндай екі әдіс – мақсаттық таг маршруты және XOR таг маршруты, олар төменде егжей-тегжейлі қарастырылады. Omega желісі жоғары дәрежеде бұғатталады, бірақ бос желіде кез келген кірістен кез келген шығысқа әрқашан бір жол табуға болады.
An 8x8 Omega network is a multistage interconnection network, meaning that processing elements (PEs) are connected using multiple stages of switches. Inputs and outputs are given addresses as shown in the figure. The outputs from each stage are connected to the inputs of the next stage using a perfect shuffle connection system. This means that the connections at each stage represent the movement of a deck of cards divided into 2 equal decks and then shuffled together, with each card from one deck alternating with the corresponding card from the other deck. In terms of binary representation of the PEs, each stage of the perfect shuffle can be thought of as a cyclic logical left shift; each bit in the address is shifted once to the left, with the most significant bit moving to the least significant bit. At each stage, adjacent pairs of inputs are connected to a simple exchange element, which can be set either straight (pass inputs directly through to outputs) or crossed (send top input to bottom output, and vice versa). For N processing element, an Omega network contains N/2 switches at each stage, and log2N stages. The manner in which these switches are set determines the connection paths available in the network at any given time. Two such methods are destination tag routing and XOR tag routing, discussed in detail below. The Omega Network is highly blocking, though one path can always be made from any input to any output in a free network.
Мақсат белгісінің маршруты
Мақсат тегін маршруттау кезінде коммутатор параметрлері тек хабарламаның түйін нүктесімен анықталады. Бірінші кезеңде коммутатордың шығысын таңдау үшін түйін нүктесі мекенжайының ең маңызды биті қолданылады; егер ең маңызды бит 0 болса, жоғарғы шығыс таңдалады, ал егер ол 1 болса, төменгі шығыс таңдалады. Келесі ең маңызды бит келесі кезеңде коммутатордың шығысын таңдау үшін пайдаланылады және соңғы шығыс таңдалғанға дейін осылай жалғасады. Мысалы, егер хабарламаның түйін нүктесі PE 001 болса, коммутатор параметрлері: жоғарғы, жоғарғы, төменгі. Егер хабарламаның түйін нүктесі PE 101 болса, коммутатор параметрлері: төменгі, жоғарғы, төменгі. Бұл коммутатор параметрлері хабарламаны жіберген түйін нүктесіне қарамастан қолданылады.
In destination tag routing, switch settings are determined solely by the message destination. The most significant bit of the destination address is used to select the output of the switch in the first stage; if the most significant bit is 0, the upper output is selected, and if it is 1, the lower output is selected. The next most significant bit of the destination address is used to select the output of the switch in the next stage, and so on until the final output has been selected. For example, if a message's destination is PE 001, the switch settings are: upper, upper, lower. If a message's destination is PE 101, the switch settings are: lower, upper, lower. These switch settings hold regardless of the PE sending the message.
XOR-белгісімен маршруттау
XOR тегінің маршрутталуында коммутатор параметрлері (көзі PE) XOR (мақсаты PE) негізінде құрастырылады. Бұл XOR тегінде ауыстырылуы керек бит позицияларында 1-лер, ал көзі мен мақсатында ортақ бит позицияларында 0-лер болады. XOR тегінің ең маңызды биті бірінші кезеңде коммутатор параметрін таңдау үшін пайдаланылады; егер ең маңызды бит 0 болса, коммутатор тікелей өтуге орнатылады, ал егер 1 болса, қиылысқан күйге орнатылады. Тегтің келесі ең маңызды биті келесі кезеңде коммутаторды орнату үшін пайдаланылады, және соңғы шығыс таңдалғанша осылай жалғаса береді. Мысалы, егер PE 001 PE 010-ға хабарлама жібергісі келсе, XOR тегі 011 болады және тиісті коммутатор параметрлері: A2 тікелей, B3 қиылысқан, C2 қиылысқан.
In XOR tag routing, switch settings are based on (source PE) XOR (destination PE). This XOR tag contains 1s in the bit positions that must be swapped and 0s in the bit positions that both source and destination have in common. The most significant bit of the XOR tag is used to select the setting of the switch in the first stage; if the most significant bit is 0, the switch is set to pass through, and if it is 1, the switch is crossed. The next most significant bit of the tag is used to set the switch in the next stage, and so on until the final output has been selected. For example, if PE 001 wishes to send a message to PE 010, the XOR tag will be 011 and the appropriate switch settings are: A2 straight, B3 crossed, C2 crossed.
Қолданбалар
Көппроцессорлы жүйелерде омега желілері процессорлар мен олардың ортақ жады арасындағы байланыс құралы ретінде қолданылуы мүмкін, процессордың жадқа қосылуының тұйыққа тірелу ықтималдығын төмендету үшін. Осы желілер класы Иллинойс Седар көппроцессорлық жүйесіне, IBM RP3 және NYU Ultracomputer-ге енгізілген.
In multiprocessing, omega networks may be used as connectors between the CPUs and their shared memory, in order to decrease the probability that the CPU to memory connection becomes a bottleneck. This class of networks has been built into the Illinois Cedar Multiprocessor, into the IBM RP3, and into the NYU Ultracomputer.