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)
  3. 14:10 Router architectures (Nikolaidou-Fotiadou)
  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):

  1. Create your own home page for this course
  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).

Lecture slides (pdf):

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

Some conferences:

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

Student pages:

  1. 90, Κων/νος Γεωργούλας
  2. 94, Μαρία Χριστοδουλίδου
  3. 98, Σπύρος-Δημήτρης Αγάθος
  4. 99, Θεοδόσης Αγγελίδης
  5. 103, Ελένη Γεωργά
  6. 106, Δέσποινα Ευγενίδου
  7. 108, Νίκος Καλλιμάνης
  8. 111, Κώστα Αναστασία
  9. 112, Κώστας Λίλλης
  10. 113, Γιώργος Λίτσιος
  11. 114, Γιώργος Μαργαρίτης
  12. 116, Δήμητρα Τσάμη
  13. 117, Γιώργος Φίλος
  14. 118, Κατερίνα Φωτιάδου
  15. Γιώργος Σταμούλης
  16. 123, Ιωάννης Ζιαγλιαβός
  17. Ε. Κοσμάς
  18. Παναγιώτα Νικολαΐδου
  19. Νότης Κάτσικος
  20. , Λαμπρινή Κώνστα