SDSU Department of Computer Science
  
Home Contact Us Undergraduate Student Info Graduate Student Info Faculty & Staff News & Events
News Calendar Problem of the Fortnight

March 2008 Calendar

CS Masters' Thesis Defense

Title: Extending the SB-PRAM Simulator to Support the Common-CRCW Processor Model
Speaker: Vidya Sarangpani
Date: Friday, March 21, 2008
Time: 12:00 p.m.
Location: GMCS 329
Thesis advisor: William Root

Abstract:
The PRAM (Parallel Random Access Machine) model of parallel computing has proven to be a rich source of theoretical results with practical applications, even though architectures supporting PRAM-like immediately-addressable shared memory only rarely have been implemented in real hardware. Thus while PRAM algorithms remain an inarguably relevant topic within university parallel computing curricula, hardware resources are rarely available on which students can actually implement and execute the PRAM algorithms that they study. The PRAM programming language Fork and the SB-PRAM Simulator developed by Jörg Keller, Christoph Keßler and Jesper Träff, together attempt to satisfy this need by providing an accurate simulator and corresponding software development environment that model the hardware PRAM prototype developed by W.J. Paul’s group at the University of Saarbrücken, Germany. The University of Saarbrücken prototype is based on the “Priority CRCW” model, in which each processor in the PRAM is assigned a unique priority, and any concurrent writes to a single shared memory location by multiple processors are resolved in favor of the highest-priority processor. Unfortunately, a substantial fraction of the PRAM programming examples used in university parallel computing courses assume PRAMs based on the “Common CRCW” model, in which unambiguous concurrent writes to a single shared memory location are allowed to proceed but ambiguous concurrent writes are not, regardless of which processors are writing. In this thesis, the SB-PRAM Simulator, originally designed to simulate only PRAMs based on the Priority CRCW processor model, was modified to simulate also PRAMs based on the Common CRCW model, thus significantly increasing the utility of the SB-PRAM Simulator as an instructional platform for university parallel computing curricula.
webmaster@cs.sdsu.edu page counter College of Sciences