|
|
|
|
|
Dragan Milicev, Ph.D. Professor
POB 35-54, 11120 E-mail: dmilicev@etf.rs Publications
on Parallel Processing |
|
|
|
Contents
This page contains references to publications and downloadable papers on parallel processing, instruction level parallelism, code optimization, software pipelining, loops with branches, and control flow regeneration.
The papers present an originally developed formal model of software pipelining loops with conditions, named Predicated Software Pipelining (PSP).
Note: Some parts of this personal home page are in Serbian. Links to these parts are labeled with (S).
Note: Papers that are submitted to conferences or journals have not been published yet. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Copyright and all rights for the papers published in journals, magazines, or conference proceedings are usually retained by the publishers. All persons copying this information are expected to adhere to the terms and constraints invoked by the copyright holders.
Note: Remarks "Recommended" refer to the publications that are recommended for initial, informative reading, in the order indicated with the associated enumeration. The others are with too much or too little detail, less up-to-date, or less interesting.
Milicev, D.,
"Parallelizing Loops with Conditional Branches," Master
thesis,
Abstract:
The thesis deals with the problem of optimizing code of program loops with conditional branches and proposes its solution. First, the thesis discusses the importance of this problem and some existing approaches to its solution. The thesis then analyzes some properties of the phenomenon, i.e., the sources of parallelism in loops with branches, and proposes a formal theoretical model for software pipelining such loops. The proposed formal model is analyzed, a definition of convergence to optimal is given, and this property is proven for the proposed model. Some heuristics for code optimizations are proposed, too, that may be used in real cases. Some proposed heuristics are experimentally evaluated and the results are presented.
Keywords: instruction level parallelism, loops with branches, code optimization, software pipelining
Download (Serbian, Zipped PDF, 520KB)
Milicev, D.,
Jovanovic, Z., "A Formal Model of Software
Pipelining Loops with
Conditions," Proc. 11th International Parallel
Processing Symposium,
Geneva, April 1997
Abstract:
This paper addresses the problem of parallelizing loops with conditional branches in the context of software pipelining. A new formal approach to this problem is proposed in the form of the Predicated Software Pipelining (PSP) model. The PSP model represents execution of a loop with conditional branches as transitions of a finite state machine. Each node of the state machine is composed of operations of one parallelized loop iteration. The rules for operation movements between nodes in the PSP model are described. The model represents a new theoretical framework for further investigation of inherent properties of these loops.
Keywords: instruction level parallelism, loops with conditional branches, software pipelining
Milicev, D.,
Jovanovic, Z., "Predicated Software Pipelining
Technique for Loops
with Conditions," Proc. 12th International
Parallel Processing
Symposium, Orlando, March 1998
Abstract:
An effort to formalize the process of software pipelining loops with conditions is presented in this paper. A formal framework for scheduling such loops, based on representing sets of paths by matrices of predicates, has been proposed. Usual set operations and relationships may then be applied to such matrices. Operations of a loop body are placed into a single schedule with the flow of control implicitly encoded in predicate matrices. An algorithm that generates loop code from such an encoded schedule has been described. The framework is supported by a concrete proposed technique that iteratively parallelize loops, as well as with heuristics driven by data dependencies to efficiently shorten loop execution. Preliminary experimental results of our prototype implementation prove that the proposed framework, technique, and heuristics produce efficient code at acceptable cost.
Keywords: instruction-level parallelism, loops with conditional branches, software pipelining
Milicev, D.,
Jovanovic, Z., "Code Generation for Software
Pipelined Loops with
Conditions," Technical Report TI-RTI-99-0041,
Abstract:
We propose a new intermediate representation for software pipelined loops with conditions. The representation allows separation of operations from different paths and their conditional, as well as speculative scheduling, including speculative IFs. We also define an algorithm that transforms the representation into the executable code. The algorithm uses the notion of finite automata to represent the execution of separate paths as threads of control that are canceled or approved by executed IF operations. The approach may be used in conjunction with modulo scheduling or other techniques to reconstruct the control flow graph from the final (modulo) schedule directly. It inherently solves the problems of overlapped predicate lifetimes and speculation. The approach provides also a novel formal model for loop execution.
Keywords: instruction level parallelism, software pipelining, loops with conditions, code generation, control flow, finite automata, predicated software pipelining, reverse if-conversion
Recommended
1
Milicev, D.,
Jovanovic, Z.,
"Sources of Parallelism in Software Pipelining Loops
with
Conditional Branches," ACM SIGPLAN Notices,
Vol. 35, No. 2,
February 2000, pp. 36-45
Abstract:
The subject of this paper is the instruction-level parallelism and the process of software pipelining loops with conditional branches. First, preconditions for treating such loops are introduced, and some effects of existence of conditional instructions and their outcomes that are important for parallelization are analyzed. These effects are emphasized and systematized.
Keywords: instruction level parallelism, scheduling, loops with conditional branches, software pipelining
Recommended
2
Milicev,
D., Jovanovic, Z., "A
Abstract:
This paper addresses the problem of parallelizing loops with conditional branches in the context of software pipelining. A new formal approach to this problem is proposed in the form of the Predicated Software Pipelining (PSP) model. The PSP model represents execution of a loop with conditional branches as transitions of a finite state machine. Each node of the state machine is composed of operations of one parallelized loop iteration. The rules for operation movements between nodes in the PSP model are described. The model represents a new theoretical framework for further investigation of inherent properties of these loops, as well as a basis for novel scheduling techniques.
Keywords: instruction-level parallelism, scheduling, software pipelining, loop, conditional branch
Recommended
3
Milicev, D.,
Jovanovic, Z.,
"Control Flow Regeneration for Software Pipelined
Loops with Conditions," International Journal of
Parallel Programming,
Vol. 30, No. 3, June 2002, pp. 149-179
Abstract:
We propose a new intermediate representation for software pipelined loops with conditions. The representation allows separation of operations from different paths and their conditional, as well as speculative scheduling, including speculative IFs. We also define an algorithm that transforms the representation into the executable code. The algorithm uses the notion of finite automata to represent the execution of separate paths as threads of control that are canceled or approved by executed IF operations. The approach may be used in conjunction with modulo scheduling or other techniques to reconstruct the control flow graph from the final (modulo) schedule directly. It inherently solves the problems of overlapped predicate lifetimes and speculation. The approach provides also a novel formal model for loop execution.
Keywords: instruction level parallelism, software pipelining, loops with conditions, code generation, control flow, finite automata, predicated software pipelining, reverse if-conversion