Integrating Task & Data Parallelism
Ian Foster (Argonne) & Carl Kesselman (Caltech)

Foster:
	Data  task parallelism lie on a continuum
	Wants to allow both

task parallel app areas
	control systems that accept nondet inputs
	irregular data structures
	multidisciplinary apps
	
task parallel problems
	too hard to do simple things (e.g. domain decomp)

            Taxonomy of two-level parallel programs:

spmd/spmd
	for calling data-parallel libraries from data-parall routines
	
spmd/mimd
	call task parallel libraries from data-parallel program
	e.g. 
		HPC extrinsic function
		collections of complex objects - partition without regard to
		nature of individual objs, then compute depending on type of each obj.

mimd/spmd
	data-parallel pipelines
		image processing
		seismic processing
	graphics
	adaptive mesh refinement

mimd/mimd
	multiple-paradigm mimd programs
	pipelined/networked mimd structures
	load balancing

spmd(r)
	any multiple-level parallel program with spmd top level

mimd(r)
	any multiple-level parallel program with mimd top level

Integrated systems

PASM
	purdue (siegel et al)
	partitionahle simd/mimd
	hardware/software comb supports both.

Data Parallel C (Oregon State)

Seevers, quinn, hatcher

add channel read/write to data parallel c.
separate coord lang def static process channel netwroks.
sequentialized intermodule communication (implementation issue).
implemented on iwarp.

looks like single-module streams - have to build data-parallle streams.

(observation:  mixed mode paradigm allows larger-grain parallelism within tasks.) 

FX

AVS as a coord lang.
syracuse
Chang, Fox and Mils

Graphical prog lang. static,acyclic task/channel structre.  
heterogeneous tasks
grapical prog environment


HPF Extrinsic procedure mechanism
  allows escape from purely data-par - allows mimd
  basically spmd block
	

Part II
Forster & Kesselman's approach

parbegin/parend for explicit parallelism
fair interleaved execution
abstarcting from environment (threads, processes) to program.
(e.g. can't assume one preocess /processor)
Need to modularize code so it can be placed in a variety of
environments

Two systems:
Modular fortran						Compositional C++

Fortran-M
Combine existing modules
Deterministic execution



CC++
Preserve C++ efficiency
Provide infrastructure for building parallel paradigmn clas libs
Extension  philosopy:based on:
	type modifiers, objects, blocks and pointers
		comm by exten of C type system
	full use of c pointers
	determinism not guaranteed unless design in
	very flexible - message-passing, rpc, data-par, etc.

Parallel blocks:
	either straigt-line code or iterations over a single statement
	assume all statemetns within block are data-independent.
	interleave arbitrarily

Comm in F-M
	Via (typed) files
	Non-array shared structure
	Data written can be re-read
	File i/O is a "logical" structure - e.g. named ports
	Can send ports over channels
	Allows dynamic process structure
	Acts like sockets (ex can send descriptors)
	Basically, processes  interface by exporting sets of ports
	This is independent of environment
	Each channel is single-sender, single receiver (at a given point in time)

Comm in CC++
	sync object = write-once future

F-M process objects
	virtual processors grouped into a machine, 
machine org. as array.
Named machines:  processors pr(NP,NP)
Allocate tasks within machines via submachines

CC++ processor object, with local variables 
Processor objs independent.  Files, globals, etc. are local to processor
objects.  
Create sets of processors, then allocate virtual machine by 
passing processor pointers around.

<missed paradigm integration in Fortran-M>

Mix hpf and fortran-m by compiling hpf to express message-passing
calls, and then (check this) translating these calls to virtual
environment

paradigm integrationin cc++

want to build libraries in cc++ and integrate
through it to allow interoperability between libraries

libraries: 
	spmd library:  processor objs, not nodes, global pointers, not node nmbers
  mimd also built in cc++; can compose with spmd libraries
	full cc++ still available

	mesage-pasing (fortran-m style channel) library
	synchronization primitive libraries
		semaphores, monitors, etc.
	self-scheduling task libraries

	data-parallel libraries
		get HPF functionality with an array!!!