Performance evaluation for deadlock detection in distributed database systems
Omran Bukhres · 1990
An active area of research in multiprocessing and distributed computing is that of mapping programs onto system architectures. Distributed programs consist of a collection of one or more tasks which must be assigned to processors and data structures which must be assigned to memory modules. The goal of this mapping is usually to optimize some performance quantity such as execution speed or system utilization. In its general form, the problem of task mapping in multiprocessors is known to be NP-complete, hence intractable. Therefore, intelligent methods are required in order to solve these problems in a realistic manner. To set the stage for these solutions, two models are developed. The first is the Enhanced Processing Network (EPN) model which is used to represent distributed architectures. The second model, called a Program Structure and Behavior (PSB) graph, allows distributed programs to be represented. The execution of PSB graphs mapped onto EPN architectures is simulated to provide performance data which is vital to the mapping problems under examination. Two forms of the mapping problem are examined. The first is unconstrained architecture synthesis. In this case, an architecture is synthesized to best suit a given program. The second form is that of constrained system mapping. This is the more conventional form where both the program and the architecture are known and the optimal mapping must be determined. In the research presented, these two mapping problems are solved using heuristic approaches which are highly effective and execute under low order polynomial time and memory complexity bounds. Examples are presented which demonstrate the effectiveness and the performance relative to deterministic methods. Theorems are developed which indicate the heuristic sets to be minimal and complete.