A Complexity Measure of Programming for Parallel Algorithm

摘要

Some algorithms are scarcely used even if they are superior in time complexity and space complexity due to difficulty of programming in parallel processing. Then, complexity measures of programming for alogorithm are needed. This paper presents a complexity (or, difficulty) measure of programming, i.e., a complexity measure of transformation from a parallel algorithm to a program, in multiprocessor parallel computers. Programming can be assumed to be easy when processes at every step in every node depend upon a simple rule (pattern). We propose a measure based on orders of functions whose variables represent node numbers and step numbers for assignment of processing nodes and arithmetic operations in an algorithm described in a Pascal style.