Brock University
Department of Computer Science

Instructor: Vlad Wojcik

DUE DATE / TIME: Friday, 26 Mar 2010, 4 PM.

THE PROBLEM:

As discussed in class, a supercomputer of N processors can exist only in finite (albeit large) number of configurations (i.e. network topologies). Its smallest number of processor-to-processor bi-directional links is N - 1 (otherwise the network will not be connected, i.e. will fall apart). A fully-connected machine of N processors has N*(N - 1)/2 links.

As N grows, the number of possible multiprocessor topologies increases. For example, peruse the table below:

# PEs	# Links	# Topos	Topologies
1	0	1
2	1	1
3	2	1
3	3	1
4	3	2
4	4	2
4	5	1
4	6	1
N	N - 1	1	linear topology
N	. . .	?	?
N	N*(N - 1)/2	1	fully connected

It is of our interest to study the properties of topologies so emerging.

THE PROGRAM:

Write the program that would study the properties of emerging supercomputer topologies as N increases. Execute the program while increasing N until the program crashes due to lack of memory. As the program executes, let it write the results into a file.

Consolidate these results in a table depicting for every N and a number of links L the number of different topologies found.

Tabulate the topologies found as follows: For every topology write its definition, diameter, bisection width and number of synonym descriptions found.

NOTE: The goal of the assignment is to analyze the tabulated results found, not to write the program. The program is only a means to the goal!

SUBMISSION FORMAT:

Both hardcopy (paper) and electronic submission is required.

Hardcopy submission: Your submission envelope with the standard Cover Page should contain all relevant printouts, demonstrating flawless behaviour of your program. The envelope should be dropped in the submission box on or before deadline date / time.

Electronic submission: Please create on your PC a sub-directory bearing your student number, place within it all the files (and only the files) to be submitted. ZIP this directory and e-mail it to your instructor (once - and only once!). The title of the message should be: "COSC 3P93: Assignment 2 Submission". The message should contain your name and student number, and the attached ZIP file.

Similarly, the electronic submission should be performed on or before deadline date / time.

Instructor: Vlad Wojcik
Revised: 10 March, 2010 1:27 AM
Copyright � 2010 Brock University