25:
144:
169:
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,
199:
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
186:
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
161:
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,
156:
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
200:
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.
190:
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.
174:
N 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.
187:
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.
203:
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.
220:
271:
230:
This class of networks has been built into the
Illinois Cedar Multiprocessor, into the IBM RP3, and into the NYU Ultracomputer.
89:
166:; each bit in the address is shifted once to the left, with the most significant bit moving to the least significant bit.
61:
261:
178:
The Omega
Network is highly blocking, though one path can always be made from any input to any output in a free network.
108:
68:
75:
46:
42:
329:
57:
212:
216:
35:
256:
133:
82:
8:
299:
Lawrie, Duncan H. (December 1975). "Access and
Alignment of Data in an Array Processor".
130:
308:
126:
281:
136:. It is an indirect topology that relies on the perfect shuffle interconnection
286:
323:
266:
163:
312:
239:
251:
158:
137:
24:
276:
162:
each stage of the perfect shuffle can be thought of as a cyclic
143:
215:, omega networks may be used as connectors between the
49:. Unsourced material may be challenged and removed.
321:
223:, in order to decrease the probability that the
181:
151:
109:Learn how and when to remove this message
147:Omega network with 8 processing elements
142:
322:
298:
47:adding citations to reliable sources
18:
262:Nonblocking minimal spanning switch
13:
194:
14:
341:
227:connection becomes a bottleneck.
23:
206:
34:needs additional citations for
301:IEEE Transactions on Computers
1:
292:
240:Omega network simulation in c
16:Form of network configuration
7:
245:
233:
10:
346:
313:10.1109/T-C.1975.224157
182:Destination-tag routing
152:Connection architecture
148:
257:Cube-connected cycles
146:
127:network configuration
330:Network architecture
43:improve this article
164:logical left shift
149:
131:parallel computing
119:
118:
111:
93:
337:
316:
114:
107:
103:
100:
94:
92:
51:
27:
19:
345:
344:
340:
339:
338:
336:
335:
334:
320:
319:
307:(12): 1145–55.
295:
282:Crossbar switch
248:
236:
213:multiprocessing
209:
197:
195:XOR-tag routing
184:
173:
159:perfect shuffle
154:
115:
104:
98:
95:
58:"Omega network"
52:
50:
40:
28:
17:
12:
11:
5:
343:
333:
332:
318:
317:
294:
291:
290:
289:
287:Network coding
284:
279:
274:
269:
264:
259:
254:
247:
244:
243:
242:
235:
232:
208:
205:
196:
193:
183:
180:
171:
153:
150:
129:often used in
117:
116:
31:
29:
22:
15:
9:
6:
4:
3:
2:
342:
331:
328:
327:
325:
314:
310:
306:
302:
297:
296:
288:
285:
283:
280:
278:
275:
273:
272:Delta network
270:
268:
267:Banyan switch
265:
263:
260:
258:
255:
253:
250:
249:
241:
238:
237:
231:
228:
226:
225:CPU-to-memory
222:
221:shared memory
218:
214:
204:
201:
192:
188:
179:
176:
167:
165:
160:
145:
141:
139:
135:
134:architectures
132:
128:
124:
123:Omega network
113:
110:
102:
99:December 2009
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
304:
300:
252:Clos network
229:
224:
210:
207:Applications
202:
198:
189:
185:
177:
168:
155:
122:
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
293:References
219:and their
69:newspapers
138:algorithm
324:Category
277:Fat tree
246:See also
234:Examples
170:and log
83:scholar
85:
78:
71:
64:
56:
125:is a
90:JSTOR
76:books
305:C-24
217:CPUs
62:news
309:doi
211:In
121:An
45:by
326::
303:.
140:.
315:.
311::
172:2
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
