Question

In the Benes network B₄ 16 inputs are matched with 16 outputs. The network can send each input to either of two copies of B₃ , which will be called the upper and lower copy. To have a congestion of 1 it is essential that any two inputs that differ by exactly 8 go to different copies of B₃, and that any two packets with outputs that differ by exactly 8 also go to different copies of B₃.

Consider the routing

Packet	A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P
Input	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Output	3	0	6	4	7	9	13	1	10	5	11	14	12	15	8	2

Here if packet _A is sent to the upper copy of B₃, then packet I must go to the lower copy (because the inputs differ by exactly 8), and packet K must go to the lower copy (because output 3 and output 11 have to be kept separate)

1) For each of the 16 inputs find the two packets that must be kept separate from it.

Packet

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Input

I

Output

K

2) Draw a graph with vertices A through P, and edges connecting packets that must avoid each other. (Note this should be one or more cycles, so draw it to be easy to see)

3) Using the graph from above partition the packets into an upper and lower set that avoids all conflicts.

Answer 1