Open AccessStatic and Dynamic Processor Allocation for Higher-Order Concurrent Languages
Author(s) -
Hanne Riis Nielson,
Flemming Nielson
Publication year - 1994
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v23i483.6976
Subject(s) - soundness , computer science , syntax , inference , process (computing) , process calculus , programming language , order (exchange) , communicating sequential processes , theoretical computer science , artificial intelligence , semantics (computer science) , operational semantics , finance , economics
Starting from the process algebra for Concurrent ML we develop two program analyses that facilitate the intelligent placement of processes on processors. Both analyses are obtained by augmenting an inference system for counting the number of channels created, the number of input and output operations performed, and the number of processes spawned by the execution of a Concurrent ML program. One analysis provides information useful for making a static decision about processor allocation; to this end it accumulates the communication cost for all processes with the same label. The other analysis provides information useful for making a dynamic decision about processor allocation; to this end it determines the maximum communication cost among processes with the same label. We prove the soundness of the inference system and the two analyses and demonstrate how to implement them; the latter amounts to transforming the syntax-directed inference problems to instances of syntax-free equation solving problems.