Class 1: Introduction

Why do we need to use parallel computers at all? The primary reason is that a number of applications that scientists and engineers are attacking these days require a tremendous amount of computing power, and traditional sequential computing is proving to be a bottleneck in the solution of these problems. Sequential computers are either too slow, or cannot meet the data I/O requirements of these applications. Let us discuss a couple of issues pertaining to these points:

1. Why can't we just keep making individual processors faster (as we have been doing for the last 50 years)? Unfortunately, we are reaching a wall of physical limitations where we soon won't be able to drive signals through circuits any faster. We have to look at other means of speeding up computers. Why do we need increased speed?
2. Grand Challenges: The HPCC (High Performance Computing and Communication) Initiative of the US Government has identified problems that will need to be solved to make US science and technology competitive and ahead of the rest of the world. These problems, however, are beyond the scope of current computing power, and innovations will have to be made to solve them. These problems include:
   • Long term weather prediction.
   • Human Genome project.
   • Ocean Circulation model.
   • Quantum Chromodynamics.
   • Oil reservoir models.
   • Aircraft simulators (Boeing 777 example).
   • Model of human vision.
   • Business applications (transaction processing systems-banks, airlines, etc.).
   Why are these problems so tough?
   Massively Parallel Computing (MPP) will be absolutely necessary to solve such problems.

Section 1.1 of [Foster] discusses the trends in applications, computer design and networking which point towards the need for parallel computing.

A little bit of history:
Computers emerged on the scene right after WWII when Eckert and Mauchly of the Moore School of Engineering at the University of Pennsylvania developed the ENIAC. There were similar developments taking place across the Atlantic in England, and John von Neumann and his colleagues developed an architectural abstraction of the computer that still describes most sequential machines (hence the name ``von Neumann Computer''). The next era of computing was dominated by the mainframes which were used for both business and scientific computing. As IC technology developed, and processors and memory became smaller, faster, more reliable and less expensive, the sizes of the computers started shrinking, while their power kept increasing. The mainframes were succeeded by minis, micros, and finally, PCs. Currently, most computing is done on individual desk top PCs and workstations. The next era of computing is sure to come from the Parallel Computing domain, as the problems that need to be solved have far outpaced the computing power that single processors can supply.

A word of warning:
It is natural to assume that just because one is using a parallel machine, there will be a considerable speedup from solving the problem on a single processor machine. This is not necessarily the case. For a parallel solution to a problem to provide any benefits, a careful design of the parallel implementation has to be performed keeping the following ``3 As'' in mind:

1. Application: The problem being solved has to be ``appropriate'' for a parallel implementation. We will learn what we mean by appropriate a little later in the course, but for now, we will just say that there should be some parallelism in the problem structure that can be exploited by the parallel machine.
2. Architecture: Once an appropriate problem is chosen, it needs to be matched to the parallel architecture that is most suited for that problem.
3. Algorithm: A carefully designed algorithm is now necessary to map the chosen application on the chosen architecture.

We will be focusing on parallel computing from the ``Computational Science'' perspective in this course. This means that we will start with an application problem in mind, and then look for computing to provide us with insights into solving the problem. Therefore, computing will join the two traditional means of looking at problems in science and engineering: theory and experimentation. The approach we will use to solve problems is based on a paradigm developed by the Undergraduate Computational Engineering and Sciences project. This paradigm defines five stages in the computational science problem-solving process:

• Problem Statement: A clear and concise description of the problem being worked upon is stated.
• Model: The problem is modeled in a format that makes its solution possible. Often, simplifying assumptions have to be made during this stage. In this course, this stage involves modeling the problem, as well as choosing the appropriate parallel computing model to solve it on.
• Method: A solution methodology is chosen to solve the problem. This phase also involves design and analysis of the algorithm to solve the modeled problem computationally.
• Implementation: The solution design is implemented on an appropriate machine using appropriate tools (compilers, debuggers, etc.).
• Assessment: This phase involves the use of techniques such as visualization to assess the quality of results achieved in the previous steps. Feedback from this phase might point out refinements that need to be made in the modeling, method (solution design), or implementation phases.

As defined above, the first phase of our computational science and engineering experience is to define an appropriate problem. Note that the problem should be such that it has the potential of benefiting from the use of high performance computing. You are encouraged to talk to possible mentors in your field of interest, and choose a project in consultation with them (please talk to me if you are interested in finding a project mentor in a particular field). Possible projects include:

• Location of buried hazardous waste using wavelets and neural networks (Misra).
• Using wavelet transforms to model Electro Magnetic scattering from rough surfaces (DeSanto and Hereman).
• Modeling the dynamics of an artificial knee from X-ray images (Rose Medical Center-possibility of funding).
• Automatic generation of parallel code to implement neural networks (Misra).
• A parallel implementation of frequency domain finite difference wave propagation (Scales).

In addition, a couple of graduate students will be working on projects that provide an opportunity for an undergraduate student to join:

• Modeling of the visual phenomenon of Hyperacuity (Olmos-Gallo).
• Parallel implementation of labeled graph matching (Abdulrahim).

Please contact me if you are interested in any of the above projects, and would like more details. Also feel free to discuss any of these projects on the newsgroup in an effort to form graduate-undergraduate teams.

Once you have chosen an appropriate project, read up on it and formulate a concise problem statement.

Reading Assignment:

1. For an excellent overview of the field of Scientific Computing, see the chapter on scientific computing in the materials developed by CU.

2. Also see the CSEP e-text for an overview of Computational Science, tutorials on some widely used Computational Science techniques, and ideas for term-projects.