The PSciCo Project

The goal of the PSciCo (Parallel Scientific Computing) project is to study how features of advanced programming languages can be used in the design of algorithms for Scientific and Geometric computing.

Project members may refer to the internal page for information about using and maintaining the web site and project volume.

Libraries and Applications

We have developed or are developing the following libraries and interfaces as part of the project.

General libraries

Arithmetic: Arithmetic on various types of extended or arbitrary precision numbers (extended floats, rationals, floats, and so forth).
Random Number Generators
Sequences: This is basically an extension of the Vector signature to include functions that more appropriate for parallel implementation.
Tables
Priority Queues
Matrix: A matrix package with both dense and sparse implementations.

Geometry libraries

The geometry libraries were designed to separate the "geometric" part (i.e., how points are located in space) from the "topological" part (i.e., information about the connectivity of simplices, polytopes, etc.)

GEOMETRY: A library of basic geometric primitives in Euclidean Space. This included operations on vectors, points, halfspaces, and other geometric objects.
PLS: Piecewise Linear System interface. The definition of polytopes in arbitrary dimensions with internal constraints.
SIMPLICIAL_COMPLEX: Simplicial complex interface.
HULL: Convex Hull in arbitrary dimension. This makes use of the GEOMETRY interface for the geometric primitives, and SIMPLICIAL_COMPLEX to define the resulting surface.

Applications

Research Papers

Guy Blelloch, Hal Burch, Karl Crary, Robert Harper, Gary Miller, and Noel Walkington.
Persistent Triangulations.
Journal of Functional Programming, 2001 (to appear).
Citation. Abstract. PS. PDF.
Perry Cheng and Guy Blelloch.
A Parallel, Real-Time Garbage Collector.
ACM Conf. on Programming Language Design and Implementation (PLDI), June 2001. 125-136.
Citation. Abstract. PS. PDF.
Guy Blelloch, Perry Cheng and Phil Gibbons.
Room Synchronization.
ACM Symp. Parallel Algorithms and Architectures (SPAA), July 2001. 122-133.
Citation. Abstract. PS. PDF.
Aleksandar Nanevski, Guy Blelloch, and Robert Harper.
Automatic Generation of Staged Geometric Predicates.
ACM International Conf. on Functional Programming (ICFP). Sept 2001.
Citation. Abstract. PS. PDF.
Umut Acar, Guy Blelloch, and Robert Harper.
Adaptive Functional Programming.
(Submitted for publication).
Citation. Abstract. PS. PDF.
Dan Blandford and Guy Blelloch.
Functional Set Operations with Treaps.
(Submitted for publication).
Citation. Abstract. PS. PDF.
Umut Acar, Guy Blelloch and Robert Blumofe.
The Data Locality of Work Stealing.
ACM Symp. Parallel Algorithms and Architectures (SPAA), July 2000. 1-12.
Citation. Abstract. PS. PDF.
Guy E. Blelloch and Perry Cheng.
On Bounding Time and Space for Multiprocessor Garbage Collection.
ACM Conf. on Programming Language Design and Implementation (PLDI), May 1999.
Girija J. Narlikar and Guy E. Blelloch.
Pthreads for Dynamic and Irregular Parallelism.
Supercomputing 98: High Performance Networking and Computing}, November 1998.

Current Project Members

Umut Acar (Graduate Student)
Guy Blelloch (Faculty)
Karl Crary (Faculty)
David Garmire (Undergraduate Student)
Robert Harper (Faculty)
Bryan Holland-Minkley (Former Undergraduate Student)
Peter Lee (Faculty)
Gary Miller (Faculty)
Aleks Nanevski (Graduate Student)
Steven E Pav (Graduate Student)
David Swasey (Research Programmer)
Noel Walkington (Faculty, Math)
Deborah Weisser (Post-Doctoral Fellow)

Former Project Members

Hal Burch (Graduate Student)
Franklin Chen (Graduate Student)
Perry Cheng (Graduate Student; PhD 2001)
Girija Narlikar (Graduate Student; PhD 1999)
Seth Porter (Undergraduate Student)

Acknowledgements

This project is supported by NSF under the title "Advanced Languages for Scientific Computation Environments" as part of the Experimental Software Systems program within CISE under grant number 9706572.

Related Projects

Last update: 30-Jul-2001 01:59 PM