Computer Science 338 Parallel Processing Williams College Spring 2006

Reminders

Your groups for the final project should now be formed. Your full proposals are due Friday, April 14.

Readings

As you do this week's readings, keep an outline of important points and points you wish to discuss during our tutorial meetings in a plain text file tut09.txt or something that can be turned into a PDF file tut09.pdf.

In addition to the text below and the web pages linked below, please read:

• Quinn Chapter 2. Do not focus too much on 2.2.
• Woodacre, Robb, Roe, and Feind, "The SGI Altix 3000 Global Shared-Memory Architecture", a White Paper from SGI from 2003. They describe SGI's successful distributed shared memory architecture. Pay particular attention to the shared memory architecture (recall that Chris Johnson mentioned "ccNUMA" a few times in his talks). The paper is here and in the file woodacre03a.pdf in the class shared area.
• Oliker and Biswas, "Parallelization of a Dynamic Unstructured Algorithm Using Three Leading Programming Paradigms" from IEEE Trans. on Parallel and Distributed Systems, Vol. 11, No. 9, pp. 931-940, 2000. This paper is in the class shared area as oliker00a.pdf. Oliker and Biswas describe implementations of a parallel application on three very different parallel architectures.

Historical Systems

• Connection Machine, by Thinking Machines. These are long, long gone. The CM-2 had 64K processors, connected in a mesh network. 2 GB memory, 10 GB disk typically. It was massive for the time (1990). CM-5 has some of the best LED displays.
• Cray, vector supercomputing. Their systems often followed the SPMD model. Cray was bought by SGI and later sold to Tera, which renamed itself Cray.
• Intel Paragon. Paragon was another mesh-interconnected system. The processors were partitioned among jobs. Intel has since gotten out of the supercomputer business, but its processors are used in many of the world's fastest computers today.

ASCI-class supercomputers: Teraflop Computing

Mid-late 1990's - the Accelerated Strategic Computing Initiative (ASCI) program from the Department of Energy program made the push for a teraflop system.

• Intel Cluster. ASCI Red, Sandia National Labs (SNL). World's first teraflop system. Linux cluster, but different from most. Its OS is based on linux, but was customized significantly. They stripped out anything that was not needed to make sure as much physical memory as possible was available for user jobs.
• SGI Origin 2000. ASCI Blue Mountain, Los Alamos National Labs. 48 128-way SMP systems.
• IBM SP. ASCI Blue Pacific, Lawrence Livermore National Labs (LLNL).

Turn-of-the-Millennium Era Systems

• PC Cluster. Try this at home. Many fall into the category of Beowulf Clusters. Bullpen is an example, though an unusual one.
• IBM SP. Basically a cluster with high-end RS6000/PowerPC processors and a high-speed switch interconnect. The switch was the key to its performance and the cause of its very high pricetag. Many of the world's top supercomputers in the early 2000's were IBM SP systems.
• SGI Origin 3000, and its predecessor, the SGI Origin 2000. The ccNUMA and NUMA-Flex systems provide non-uniform shared memory access. These systems were popular among those who preferred threads to MPI.
• IBM was selected to build ASCI White, at LLNL, the second generation ASCI platform. A smaller version is Blue Horizon at San Diego Supercomputing Center (SDSC), available to a wider group. Larger clusters built using larger SMPs. Single-node processor utilization is important, but may be difficult to achieve.
• Number one on the Top 500 Supercomputers for a while was Terascale at Pittsburgh Supercomputing Center. It was nicknamed "LeMieux" for obvious reasons. This system was built from Alpha processors.
• Chiba City at Argonne. A big cluster.
• CPlant at Sandia takes the cluster idea to a new level. The cluster is designed to evolve over time, by adding new (faster, cheaper) nodes and pruning off obsolete parts. This "pruning" can be done without reconfiguring the rest of the cluster.

Issues for Cluster-based Systems

• Assignment of nodes to jobs - we want to keep as many nodes as possible busy computing, but we don't want to let small jobs (few processors) starve larger jobs (many processors).
• Some jobs may require special resources available only on some nodes - for example in the bullpen cluster, some nodes have 4 processors while others have two, some nodes have more memory than others, and some nodes have a gigabit interconnect and others don't.
• A scheduler might require jobs submissions to include a maximum running time to be able to schedule more intelligently.
• Scheduling is likely non-preemptive, but we can consider a "shortest job first" approach.
• These issues are addressed by the Maui Scheduler
• Another issue: are compute nodes granted exclusively to one job, or are they shared?

Today's Best

Check out the most recent Top 500 Supercomputers released in late 2005. In particular, look at the architectures of the top 10.

But what exists "inside the fence?" Certainly some government or military agencies have more powerful versions of these computers available, but not public.

Something Different

• TeraGrid: An Internet "cluster of clusters".

  Many new issues arise here - it is no longer a resource stored in one building in one place with one adminstrative entity. We need to worry about scheduling on a larger scale. User authentication. Use of computers at multiple sites simultaneously will involve slow wide-area network links. How to get the data to the computers, where to store results?

  If this is of interest, we can talk about it some more in an upcoming week.

• Tera/Cray MTA. Only one MTA-1 was ever in production, SDSC. The operating system is MTX, a fully-distributed Unix variant. The system is thoroughly multithreaded, with each "processor" actually consisting of a number of streams, each of which is fed the code and data to do some part of the computation. A sufficiently multithreaded application can keep most of these streams busy, meaning that the penalty we usually pay for memory latency is gone. In fact, the system has no traditional memory cache, since it can rely on this multithreading to mask memory latency. The MTA-2 has since arrived. Its architecture is similar to the MTA-1, but it's all CMOS instead of GaAs.

  A little more from a Cray developer:

  The MTA-2 is quite different. The instruction set is the same as in the MTA-1. But the MTA-2 is built from all-CMOS parts. It also has a completely different mechanical structure, and a completely different network structure. It can also handle more memory, I believe. Processor boards come in groups of 16 called "cages." Each processor board (we call them system boards) has one CPU, two memory controllers, one IOP. Those four entities are called "resources." Each resource is attached to a network node. The network nodes are connected to each other in a ring on the system board, and to other boards with various kinds of inter-board connections.

  The MTA system is fully scannable, i.e., with few exceptions, every flop in the machine can be written and read by diagnostic control programs. This is how we boot the machine - essentially we write the state we want into the machine, and then say "go." When we bring the machine down we read the state out and can get diagnostic information that way. We use the scan system heavily - for booting, part testing, development, all kinds of things.

Submission and Grading Guidelines

Before your tutorial meeting, submit a plain text file tut09.txt or a PDF file tut09.pdf that contains the outline that you will use to help guide our discussion. You may choose to work with your tutorial partner(s) or independently on this outline. Your grade for the week will be based on the quality of this outline.