Computational Science Qualifying Exams August 1999

.

The August exam will have one compulsory question covering all aspects of the interface of computer science with applications. A broad knowledge of parallel computing and web technologies will be needed to answer this.

Then students will choose between two sets of about 6 questions

Set I will cover material at level of CPS615 as taught last two years

 

Set II will cover material at level of CPS616 as taught this semester: see

http://www.npac.syr.edu/Education/Courses/CPS616/index.html

One must answer either set I or Set II but not both

Thus one expects that good knowledge of either CPS615 or CPS616 combined with selected general reading outside courses is needed for the computational science exam.

Sample Questions

These sample questions may not be correct level and we reserve right to make them easier or harder. However they do illustrate type of questions you can expect.

As explained above, the first question in each set is identical as it embodies aspects of both tracks. It is also compulsory.

Sample Question Set I: Computational Science Simulation Track

Answer Question 1 and any 4 of the following 5 questions.

  1. Some of the best-known search engines on the web are implemented at the backend by a cluster of 100 PC's with very fast message passing interconnects. Abstract this problem as N users searching M datasets to find those datasets, which contain a particular word. The PC clusters store these datasets in some suitable form after they have been fetched from the web by a robot. Your contract with the host site guarantees that you will give a response in less than one fifth of a second and you are to return the best 100 matches of search words to datasets. Design a parallel algorithm that will make you as rich as possible. You should only address the search problem and not the robot gathering problem. Discuss the different forms of parallelism possible - over users and over datasets. You can ignore the in practice critical issue of fault tolerance. You are paid by those that advertise on the originating page $1 for every 1000 "clicks" of the search button. If it helps M is 10**8 with total size of one terabyte and there are 10**7 separate words that can be searched on. Estimate how much money you will make in a year if machine runs for a year and does not crash.
  2. We are simulating the evolution of globular clusters with time. These can be viewed as a collection of one million point particles (stars) interacting with a known long range force. Describe a suitable parallel algorithm for this problem using the basic O(N**2) algorithm for the interaction of N bodies.
  3. Describe the following four parallel computing architectures a) distributed memory b) shared memory symmetric multiprocessor c) distributed shared memory d) SIMD. Give a real world example of each. Contrast the use of these architectures on the problems described in 1) and 2).
  4. MPI (Message Passing Interface) and HPF (High Performance Fortran) are two well known parallel computing programming models. Describe and contrast them explaining how they can be generalized as message parallel and data parallel models for any base language.
  5. In the year 2007, your start up produces a nifty new processor chip with 500 million transistors. You design a chip containing 50 separate CPU's each being an optimized processor for the Java Virtual Machine. Describe how this processor would support parallelism and when you would expect to see speedups near 50. In the year 2007, assume that Java will be the only language used and Linux the only operating system. Assume that Microsoft will have gone bankrupt and that important applications such as word processing will be rewritten in Java and exploit threads available in this language. Choose any 3 important applications to illustrate your discussion.
  6. Data locality is critical to ensuring high performance for both caches and parallel systems. Describe this in detail.

 

Sample Questions Set II: Computational Science Information Track

Answer Question 1 and any 4 of the following 5 questions.

  1. Some of the best-known search engines on the web are implemented at the backend by a cluster of 100 PC's with very fast message passing interconnects. Abstract this problem as N users searching M datasets to find those datasets, which contain a particular word. The PC clusters store these datasets in some suitable form after they have been fetched from the web by a robot. Your contract with the host site guarantees that you will give a response in less than one fifth of a second and you are to return the best 100 matches of search words to datasets. Design a parallel algorithm that will make you as rich as possible. You should only address the search problem and not the robot gathering problem. Discuss the different forms of parallelism possible - over users and over datasets. You can ignore the in practice critical issue of fault tolerance. You are paid by those that advertise on the originating page $1 for every 1000 "clicks" of the search button. If it helps M is 10**8 with total size of one terabyte and there are 10**7 separate words that can be searched on. Estimate how much money you will make in a year if machine runs for a year and does not crash.
  2. In practice, the engine in question 1) uses no conventional databases but optimized flat files. However imagine that we wished to produce a solution where each PC used JDBC to access a database (a separate one on each PC) and the PC's coordinated using RMI to communicate between PC's. Each PC runs an Apache web server. Explain this implementation in detail
  3. Contrast the use of RMI, CORBA and CGI Mechanisms in implementing web-linked databases.
  4. The attached HTML page and JavaScript code (in WWexamutility.js file) illustrates some simple concepts in dynamic HTML. Explain this by adding a comment to each line of the JavaScript in the HTML page cpsqualhtmlfile.txt and a comment for each method in the WWexamutility.js file.
    These files are separate documents and can be browsed directly as cpsqualhtmlfile.txt and WWexamutility.txt .
  5. Consider two simple problems a) calculating the sum of the first 200 integers and b) finding if a given character string contains another character string. Write this in Java JavaScript and either Perl Fortran or C.
  6. Consider a credit card. Design an XML representation of the information that it represents. Describe some money making web applications that could use this XML description.