Computational Science Exam August 26 1999 questions

Anwser Question 1 and at most 5 of the 6 following questions in either Track I or Track II
You cannot mix or match -- either choose track I OR track II

The Question Common to both tracks
1: Consider the following practical computing concepts, technologies and/or systems
a) JavaRMI
b) MPI
c) Fortran
d) C++
e) World wide Collection of 100 million Web Clients
f) Cray T3E or IBM SP2 Parallel Computer
g) A Network of 256 PC's connected via ATM 
h) Compiler
i) Just in Time Compiler
j) Interpreter

Explain these concepts and define any acronyms
Further we can think of 5 issues
A) Performance
B) Message Passing Protocols
C) Parallel Computing
D) Distributed Computing
E) Programming Environments

Use these and any other issues you think important to compare 
the technologies/systems a) to j). Obviously not all issues are
relevant for each of the entities a) to j).

Track I: Based Mainly on CPS615
2: Give an efficient parallel algorithm that will scale to many nodes on a suitably large
problem for one ( and ONLY one) of the four following algorithms
a) Fast Fourier Transform
b) Sorting for an algorithm which has O(NlogN) complexity on a sequential machine.
c) Unbiased Random Numbers
d) Conjugate Gradient Iterative algorithm for solving Partial Differential Equations
Describe the computer architecture issues (which type of machine is suitable and if good
communication important)

3: Your genius has been recognized and you have been hired away from Syracuse University (this
will only happen if you pass this exam) with a more less infinite salary and a budget of $500M
to design and build two prototypes of the next 100 teraflop computer to be delivered to the
US Department of Energy in 2004. Describe the hardware and software issues of your system design.
Assume if you want that major application is weather forecasting. 
Describe the characteristics of system
How much memory/How many nodes/Topology/Shared or Distributed Memory Architecture etc.

4: High Performance Computing Systems and technologies promise the ability to implement
services of great value to society. consider the world or any region of it such as your
favourite country. Explain how a parallel computing system can effectively improve the quality
of life of the people. Approximately 50% of credit will be given for concept and an
explanation of its importance. The other 50% of credit will be given for technical explanation
of system design. Estimate size of system needed for your application.

5: Programming example
In this question, you are to write a program that computes
the mean and standard deviation of an array of numbers on a set of N
processors.  This program is to be written in C or Fortran using MPI calls.  

In the program you may use the following basic 6 MPI calls, given 
here with the C binding:

int MPI_Init (int *argc, char ***argv)
int MPI_Finalize (void)
int MPI_Comm_size (MPI_Comm comm, int *size)
int MPI_Comm_rank (MPI_Comm comm, int *rank)
int MPI_Bcast (void *buf, int count, MPI_Datatype datatype, int root,
               MPI_Comm comm)
int MPI_Reduce (void *sendbuf, void *recvbuf, int count, 
                MPI_Datatype datatype, int root, MPI_Comm comm)

To solve the problem, assume that one processor, which we may call
processor 0, has an array initialized with floating point numbers.
The computation of the mean and the standard deviation of the numbers
will take place in parallel on all N processors, and the result will
end up on processor 0.  Please include with your code a description of
the decomposition of the problem onto processors and of the dataflow
involved in the message passing.

Note that since you will be writing this program on paper, we will
not deduct points for simple syntax errors, but will primarily grade
your solution on the basis of your understanding of using MPI in the
parallel solution of this problem.

6: Derive the performance of a two dimensional parallel Jacobi algorithm 
on a parallel computer with
a) 2D mesh interconnect
b) N nodes with 1<=N<=1024
c) m by m grid of field values in problem (take m=1024 for specificity leading to over a
   million grid points)
d) each node of machine able to perform a floating point add or multiply in TF microseconds
e) Node to Node communication channels able to transmit W words in TB*W microseconds

Remember that Jacobi's method to solve partial differential equation operates on a finite
difference grid and in two dimensions is an iterative loop where the field value at each
grid point is replaced in two dimensions by the average of its 4 nearest neighbors. By performance, we mean estimate relative performance on a parallel machines (compared to a
sequential machine) as a function of N m TF and TB

7: Consider 3 types of Problems
a) Synchronous
b) Loosely Synchronous
c) Pleasingly or embarassingly parallel

Consider 3 problems
x) Parallel Web (HTTP) Server
y) Solution of N-body problem with Parallel "Fast Multipole" (sometimes known as Barnes-Hut)
   algorithm in astrophysics
z) Solution of N-body problem with O(N*N) classic parallel
   algorithm in astrophysics (used when density extremely variable)
 
Consider 2 machine architectures
1) MIMD
2) SIMD

A) Describe which problems run on which machine architectures and fall in what problem class.
B) Decsribe the essential features of the parallel implementations of each problem
   (decomposition, communication and performance issues etc.)

--------------------------------------------------------------------------------------------------
Track II: Based Mainly on CPS616

2: Distance education has succeeded and the Fox's Den Virtual University (FDVU) educates one
million students per year. These students make use of a Web portal to access the curriculum,
grades etc. which are stored in a backend database.
Central to FDVU is a multi tier database system using JDBC and Servlets. Describe this
architecture and explain 2 3 and 4 tier systems. Explain in each case where you use Java, SQL,
XML, HTML and JavaScript. Do you need any other technologies?
Discuss the relevance of parallelism in order to support this rather large student body
Describe what difficulties one might encounter.

3: Your genius has been recognized and you have been hired away from Syracuse University (this
will only happen if you pass this exam) with a more less infinite salary and a budget of $500M
to design and build the Washington Intranet capable of running the US Government and its
service to the people. Describe the hardware and software issues of your system design. You
should have servers, networks and clients. Define any key object abstractions.
Assume if you want that major application is servicing health care claims with use of nifty AI
algorithms to detect fraud which is meant to be currently some $100 Billion per year.
Describe the characteristics of system
How much memory/How many nodes/Topology/Shared or Distributed Memory etc.

4: Distributed Object and Web technologies promise the ability to implement services
of great value to society. consider the world or any region of it such as your favourite
country. Explain how an object web system can effectively improve the quality of life of
the people. Approximately 50% of credit will be given for concept and an explanation of
its importance. The other 50% of credit will be given for technical explanation of system
design.

5. Programming question.
In this question, you are to write a program that displays
to the user two textfields and a button on an HTML page.  This can be 
written either in Java or in JavaScript.  If written in Java, this
will be an applet.  If written in JavaScript, this will be an HTML
page with JavaScript in it.

The program should behave as follows:  the user should type in a
number in the first textfield which is interpreted as degrees Fahrenheit,
when the user clicks the button, the number is converted to degrees
Centrigrade and displayed in the second textfield.  In addition, if
using JavaScript, the program should validate the input from the textfield
to make sure that the input is not empty and is a positive integer.
Please include with your code a description of how the event handling
is taking place, and in the case of JavaScript, how your program uses
the Document Object Model.

Note that since you will be writing this program on paper, we will
not deduct points for simple syntax errors, but will primarily grade
your solution on the basis of your understanding of placing GUI elements,
doing event handling, and in the case of JavaScript, the Document 
Object Model.

6: Consider any country that exists. State the name of this country and then design an XML
representation of its government. 
This is a set of tags and attributes such as the the following example
<senator name="Hilary Clinton" State="NY" election="00" >Only a Conjecture</senator>

State the DTD for your representation. Your set of tags/attributes should be valid
through multiple elections (revolutions or whatever changes government) with an
election changing attribute values but not needing new tags. Give an example and explain
the structure of your representation. For this question 40% of credit will be for DTD, 35%
for explanation and 25% for example. Obviously you can go down to an indefinite depth in this
representation. Stop when when you have spent a reasonable time on question and exercised what
you know about XML. (We will judge on quality of XML and not size of bureaucracy represented)

7: The Real World -- Answer two of a) b) c) or d)
a) Sun MicroSystems, Silicon Graphics (SGI), Oracle, Yahoo, American Online, Microsoft
   and Oracle are more or less succesful in today's Internet. Contract their successes and
   failures and their different strategies and market positioning.
b) Describe issues connected to placing 2D and 3D Images on the Web. Discuss (Animated) GIF,
   JPEG, VRML, Java3D and other technologies you think important
c) What is Dynamic HTML. Why is it important. Where is it going?
d) Describe and contrast 4 distributed object approaches (CORBA, COM, Java, XML)