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 Only a Conjecture 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)