Computer Science 338 - Spring 2006

Parallel Processing

Williams College

Final Projects

Marcus Duyzend '06

Title: Simulating Multicomputers and Multiprocessors: Extensions of the WC34000 Simulator
Abstract: The WC34000 is a simple, simulated processor used for instructional purposes. I discuss the design and implementation of two extensions to the WC34000 simulator. The first extension allows the simulation of a centralized multiprocessor consisting of an arbitrary number of WC34000 processors with a shared memory space. The second extension allows the simulation of a distributed multicomputer consisting of an arbitrary number of processors, each with its own local memory, that communicate with each other by means of explicit message passing. This second extension uses the WC34060, a modification of the WC34000 with an instruction set that provides message passing capabilities.

Robin Stewart '06

Title: Parallel Approaches to Natural Language Parsing
Abstract: Parsing natural language is the task of inducing the syntactic or semantic structure of sentences in English or any other human language. It plays an integral role in most systems that try to understand natural language. But for real-time dialog applications in particular, even the best serial parsing algorithms on the best serial hardware cannot process sentences fast enough at the level of parse quality desired. The approaches which have had the most success at speeding up parsing have relied on parallel machines with a high degree of connectivity and parallel algorithms highly tuned to the nature of the parsing task. I focus my discussion on one such design: a popular and parallelizable algorithm for natural language parsing called chart-based parsing.

Jing Cao '08, Arjun Sharma '07, Jan Zankowski '07

Title: Shotgun Sequencing In SALSA: Using SALSA To Parallelize The Recreation of A Play From Garbled Sequence of its Pieces
Abstract: The aim of this project paper is twofold. First, we present the results of our experiment with the parallelization of the DNA Shotgun Sequencing algorithm. Second, we discuss our use and evaluation of SALSA, a new Actor Oriented language, as a parallelization tool.

Mitch Brooks '07, Ian Jessen '07, Mark van Mechelen '07

Title: General Purpose Graphics Processor Unit Computing: SIMD Parallel Processing
Abstract: In an increasingly demanding market for graphics hardware, Graphics Processor Units, or GPUs, have become standard equipment on most PC's. In this paper, we explore some of the advantages and disadvantages of working with the GPU for general computing. To accomplish this we implemented a program that uses the GPU to do scaled vector addition. The primary purpose of this program is to demonstrate the computational horsepower of the GPU. The results demonstrate that for large, data parallel computations with minimal CPU communications, the GPU is an enormously powerful tool. It is, however, important to note that few scientific problems map perfectly to the GPU as many require advanced data structures not natively supported by the GPU. Additionally, the many components involved -- shader languages, API, extensions, and hardware -- contribute to the difficulty of GPGPU programming. However, there is prospect for a brighter future as both problems are being addressed: Libraries of generic random-access data structures are in development, and stream programming languages, which will abstract the stages of GPU programming, are also under development.

Michael J. Gnozzio '07

Title: Parallel Fractal Generation in Cocoa
Abstract: Since its transition to OS X in 2001, Apple has encouraged programs to develop software in Objective-C using a framework known as Cocoa. This paper explores native support for parallelism in Cocoa through the context of a fractal program which creates fractals from a generator curve input by a user. First, it considers the use of threads in Cocoa and discusses the implementation challenges and successes of creating serial and threaded versions of the aforementioned program. Then, it goes on to examine opportunities for additional parallelism in Cocoa resultant from Apple's built in support for grid technologies in OS X and OS X Server. The threaded fractal program is converted into a grid based one using the programmatic Xgrid framework which Apple is now including with all of its development tools. Performance results comparing the serial, threaded, and grid versions of the program are presented. Finally, the paper suggests ways for improving upon the Xgrid framework.

Jessica Chung '07

Title: Pairwise Sequence Alignment in Parallel
Abstract: Basic local alignment search tool (BLAST) is a program used to compare two sequences. Particularly, BLAST can be used to compare strands of nucleotides (DNA) and proteins. BLAST uses an heuristic version of the Smith-Waterman dynamic programming algorithm. Recently, a parallel version of BLAST, mpiBLAST, has been developed using the message-passing language MPI. MpiBLAST exhibits superlinear speed-up due to its partitioning of the databases of nucleotides and proteins. Additonally, mpiBLAST has since been extended, as mpiBLAST-pio, with parallel input/output functionality. For this pro ject, two similar pairwise sequence alignment algorithms were implemented in serial, and parallelized using OpenMP directives and Posix threads. The results of running these programs on the Williams College Department of Computer Science resources are compared.

Stephen Abbott '07

Title: Parallelism in Personal Computing
Abstract: Throughout recent decades, the speed of personal computers has risen at an incredible rate. The Apple II, one of the first successful personal computing machines, was released in 1977 (Steve Wozniak). The processor of this state of the art machine was 1 MHz. By comparison, today's top of the line personal computers can exceed 3 GHz. This amazing increase in speed has been one of the primary factors in the computing revolution which has overtaken the world. From word processing to the Internet, personal computing has revolutionized the way in which modern people work and interact. However, the advances made by processor speeds alone have a physical upper bound. Based on trends set in the 1990's, one would expect that there would be 10 GHz processors on the market today; rather, chip design has hit a wall during the past few years (Herb Sutter). While CPU speeds are still being expanded through advances in chip design, transistor speeds and advances in memory, people have already begun to look towards parallelism as a new way of increasing the capabilities of personal computers (Herb Sutter). Intel is one of the current leaders in bringing parallelism to personal computers, having thus far implemented two radically different forms of parallelism: hyper threading and multicore processors.