BSPk: Low Overhead Communication Constructs and
		    Logical Barriers for
	    Bulk Synchronous Parallel Programming

	Amr Fahmy			Abdelsalam Heddaya
	amr@das.harvard.edu		heddaya@cs.bu.edu
	
	Aiken Computation Lab		Computer Science Dept.
	Harvard University		Boston University


Communication and synchronization stand as the dual bottlenecks in the
performance of parallel systems, and especially those that attempt to
alleviate the programming burden by incurring overhead in these two
domains.  We formulate the notions of {\em communicable memory} and {\em
lazy barriers} to help achieve efficient communication and
synchronization.  These concepts are developed in the context of BSPk a
toolkit library for programming networks of workstations---and other
distributed memory architectures in general---based on the Bulk
Synchronous Parallel (BSP) model.  BSPk, whose design is the subject of
this paper, emphasizes efficiency in communication by minimizing local
memory-to-memory copying, and in barrier synchronization by not forcing
a process to wait unless it needs remote data.  Both the message passing
(MP) and distributed shared memory (DSM) programming styles are
supported in BSPk, for the former helps processes exchange short-lived
unnamed data values, while the latter permits communication through
long-lived named variables.