Universitatea Babeş-Bolyai Cluj-Napoca
Facultatea de Matematică şi Informatică
Ciclul de studii: Masterat
Domeniul: Informatica
Programul de studii: Programare bazata pe componente - în limba engleză
Limba de predare: Engleză

SYLLABUS

I. General data
Code	Subject	
MID1005	Formal Methods in Parallel Programming	

Semester	Hours: C+S+L	Category	Status	
4	2+2+0	specialty	compulsory	

II. Full status faculty members
Name and	Scientific	Didactic	Chair	Type of activity	
surname	title	title		C	S	L	
Niculescu Virginia	Ph.D.	Assoc. Prof.	Programming  Languages and Methods	*			

Associated faculty members
Name and	Scientific	Institution	Type of	Type of activity	
surname	title		position	C	S	L	

III. Course objectives
•	To present theoretical foundations of parallel algorithms construction. 
•	To present different formal methods of correct development of parallel programs. 
•	To offer the possibility of learning different formal methods of correct development of parallel programs, and understanding their necessity and their advantages.
•	To create the ability to correctly develop parallel algorithms based on different formal methods (algorithms from linear algebra, numerical analysis, graph, searching and sorting algorithms).

IV. Course contents
This course covers theoretical foundations of parallel programs. 
The emphasis of this course is on the design and analysis of parallel algorithms. 

Different formal methods of correct development of parallel programs are presented. The derivation process of parallel programs is more rigorous and simple if these methods are used, but the most important thing is that assure the correctness. Correct derivation is essential for parallel programs since the debugging is extremely difficult for them.  Also for developing parallel programs we cannot base only on intuition, and formal methods could lead to efficient solutions.

0. General introduction to parallel programs development
1. UNITY "Unbounded Nondeterministic Iterative Transformations" 
2. A Method Based on Development from Specifications. 
3. Bird-Meertens Formalism (BMF). 
4. Special Data Structures for Parallelism. 
5. General presentation of the existing parallel computation models.

V. Bibliography
1. K.M. Chandy, J. Misra, Parallel Program Design: A Foundation, Addison-Wesley, 1988.
2. J. Misra. PowerList: A structure for parallel recursion.ACM Transactions on Programming Languages and Systems, 16(6):1737-1767, November 1994. 
3. V. Niculescu. Calcul Paralel. Proiectare si dezvolare formala a programelor paralele. Presa Univ. Clujana, 2006.
4. D. Skillicorn. Foundations of Parallel Programming, Cambridge International Series on Parallel Computations, 1994
5. D.B. Skillicorn, D. Talia. Models and Languages for Parallel Computation. ACM Computer Surveys, 30(2) pg.123-136, June 1998. 	

VI. Thematic of didactic activities per weeks
(C1-C14 lectures, S1-S14 seminars)  one course and one seminar/ week

C1- General Introduction to parallel programs development 
  Phases in parallel programs development [3]

C2-C4
1. UNITY"Unbounded Nondeterministic Iterative Transformations" [1] [3, ch.5]
1.1	UNITY programs notation
1.2	Prooving rules
1.3	Mapping
1.4	Examples

C5-C7
2. A Method Based on Development from Specifications. [3, ch. 6]
	2.1 Functional specifications/ Invariants
2.2 Program notation
2.3 Prooving rules
2.4 Communication processes
2.5 Time-compexity analysis
2.6 Data-Distribution 
2.7 Examples

C8-C9
3. Bird-Meertens Formalism (BMF). [3, ch 7] [4]
3.1 List Homomorphisms
	3.2 Categorical Data Types
	3.3 Examples

C10-C12
4. Special Data Structures for Parallelism. [2] [3, ch 8]
	4.1 PowerLists
	4.2 ParLists
4.3 Plists
4.4 Fast Fourier Transformation – derivation based on these structures
4.5 Multidimensional Data Structures
C13-C14
5. General presentation of the existing parallel computation models. [5] [3, ch 9]

	5.1 Requierements for PCM
	5.2 Classification:	
		- implicit parallelism 
		- implicit decomposition 
		- explicit decomposition
		- explicit mapping 
		-explicit communication 
		- everything explicit

Seminar
S1  Phases in parallel program construction. Simple parallel programs. 
S2  Divide&Impera. Pointer Jumping. Binary-tree technique. Ascending/descending algorithms.
S3 Examples of UNITY programs development
S4-S5 Examples of program development from formal specifications
S6 Applications of BMF formalism
S7-S8 Applications of PowerList/ParList/Plist structures
S9-S14 Students’ project presentation

VII. Didactic methods used
Expositions: description, explanation, class lectures, dialog-based lectures, introductive lectures, current lectures, synthesis lectures. 
Conversations: debate, dialog, introductive conversations, conversations for knowledge consolidation, conversations to systematize and synthesize knowledge 
Use of problems: use of problem questions, problems and problem situations. 
Discovery: directed and independent rediscovery, creative discovery, inductive discovery, deductive discovery, experimental discovery. 
Other methods: case study; cooperation, brainstorming, individual study, exercise, homework study.	

VIII. Assessment
The final mark will cover lab work (i.e. completing a project) and research work (preparing a research paper), as well as the written exam results. It is computed as follows, on a 10-point scale:
•	1pt by default
•	1pt attendance
•	2pts the project
•	3pts the paper
•	3pts the written exam.	

IX. Additional references
1. Ian Foster. Designing and Building Parallel Programs, Addison-Wesley 1995. 
2. A. Grama, A. Gupta, G. Karypis, V. Kumar. Introduction to Parallel Computing, Addison Wesley, 2003.
3. L.D. Loyens, A Design Method for Parallel Programs, PhD. Thesis, University of Eindhoven, 1992. 
4. V. Niculescu, Modele de elaborare a algoritmilor paraleli, PhD. Thesis, Univ. Babes-Bolyai, 2002.
5.  J. Kornerup. Data Structures for Parallel Recursion. PhD thesis, Univ. Of Texas at Austin, 1997.	

	Date,							Course responsible,
	15.04.2007						Assoc. Prof. Niculescu Virginia, Ph.D.