HOME
Αρχική

TEACHING
Διδασκαλία

RESEARCH
Έρευνα

VARIOUS
Διάφορα

## Y-12 Topics on Parallel Architectures: Interconnection Networks Spring 2006

#### Project presentation schedule (approximate):

1. 13:30 Hypercube variants (Margaritis-Kosmas)
2. 13:50 Rearrangeable networks (Konsta-Xristodoulidou)
4. 14:30 Booksim simulator (Agathos-Kallilmanis)
5. 14:50 Deadlocks in routing (Evgenidou-Stamoulis)
6. 15:10 Fault tolerant routing (Litsios-Aggelidis)
7. 15:30 Multiprocessors-in-a-chip (Georga-Filos)
8. 15:50 Networks-on-chip (Georgoulas-Kastikos)
9. 16:10 Optical MINs (Kosta-Tsami)

#### -- ΑΝΑΚΟΙΝΩΣΗ --

Αν την Τρίτη 23/5/2006 συνεχίζεται η κατάληψη του κτιρίου, την ώρα του μαθήματος (12:00), θα συναντηθούμε στην καφετέρια του Σπύρου (κτίριο νέων εστιών, απέναντι από το Μεταβατικό) όπου και θα οριστικοποιηθούν τα projects.

>> Οι καφέδες κερασμένοι!

#### Assignment 6 (due 23/5/2006):

1. ("teaching" assignment): three 45min lectures on deadlocks in routing

#### Assignment 5 (due 9/5/2006):

1. Find which destination bit is used for routing in every stage of the following 8 multistage networks: omega, baseline, multistage n-cube, butterfly and their inverse networks.
2. Summary of the two papers we talked about in the class

#### Assignment 4 (due 18/4/2006):

1. Prove that if b(i) (corr. g(i)) is the i-th bit in the n-bit binary (corr. Gray-code) representation of a nuumber, then g(i) = b(i) XOR b(i+1), with g(n-1) = b(n-1).
2. Write (in C) a program that maps arbitrary meshes / tori to a hypercube using Gray codes and partial Gray codes

#### Assignment 3 (due 11/4/2006):

1. Summary of the paper we talked about in the class

#### Assignment 2 (due 4/4/2006):

1. Line graphs:
1. Prove the formula for the number of edges in a line graph/digraph
2. Give the number of vertices, number of edges, degree and diameter for deBruijn and Kautz graphs
2. Cartesian product:
1. Prove that G1*G2 = G2*G1
2. Give a formula for the number of edges in the cartesian product of k graphs
3. Give a formula for the mean distance in a 2D product (assume you know the average distance in each dimension). Then, give a formula for the mean distance in an MxM mesh and in an MxM torus.
4. Can you find a general formula for k dimensions?

#### Assignment 1 (due 21/3/2006):

2. Calculate the mean distance in linear arrays and rings
3. Find all proposed interconnection networks (in journals and conferences) during 2000-2005 (due 28/3/20006).

#### Some books:

• J. Duato, S. Yalamanchili, L. Ni, Interconnection networks: an engineering approach, Morgan Kaufmann, 2003
• W. Dally, B. Towles, Principles and practices of interconnection networks, Morgan Kaufmann, 2005
• J. Xu, Topological structure and analysis of interconnection networks, Kluwer, 2001

#### Some journals (UoI has online access):

Notice that IEEE journals/conferences should preferably be accessed through http://ieeexplore.ieee.org, NOT through http://www.computer.org/portal/site/csdl (Computer Society's Digital library) due to access problems.

• IEEE Transactions on Parallel and Distributed Systems
• Journal of Parallel and Distributed Computing
• Journal of Interconnection Networks (JOIN)
• IEEE Transactions on Computers
• Parallel Processing Letters
• Parallel Computing

• IPDPS
• ICPP
• EuroPar
• SPAA
• PDCS
• HiPC
• ...