International Journal of High Speed Computing

The increasing complexity of parallel computing systems has brought about a crisis in parallel performance evaluation and tuning. Tools for performance measurement and visualization become necessary parts of programming environments for parallel computers. In this paper we describe a tool — which we call the Performance Adviser — that offers two different levels of performance information (high level and low level), guides the users to specific problem areas in the source code, and suggests actions to improve the performance of their parallel programs. Working behind the Performance Adviser is an expert system which derives high level concepts from the source code and a critical path analysis metric which derives low level performance information from the performance data collected in the execution of the program.

In this paper, we describe a methodology for mapping normal linear recurrence equations onto a spectrum of systolic architectures. First, we provide a method for mapping a system of directed recurrence equations, a subclass of linear recurrence equations, onto a very general architecture referred to as basic systolic architecture and establish correctness of the implementation. We also show how efficient transformations/implementations of programs for different systolic architectures can be obtained through transformations such as projections and translations. Next, we show that the method can be applied for the class of normal linear recurrence equations using the method for the class of directed recurrence equations. Finally, we provide a completely automated procedure called cubization to achieve better performance while mapping such equations. The method is illustrated with examples and a comparative evaluation is made with other works.

A directed acyclic task graph (DAG) contains a set of tasks which access a set of data items and perform certain computations on those data items. The problem of DAG scheduling that optimizes the assignment of tasks onto the given processors has been studied extensively in the literature. We have developed a DAG scheduling system called PYRROS that maps the computation of task graphs onto message-passing machines [24]. In this paper we present a schedule executing model that incorporates several optimization strategies to reduce communication overhead and improve memory utilization. We study the correctness of task graph execution using this method and generalize this result to the iterative execution of a task graph and present experimental results on an nCUBE-2 parallel machine.

The performance of various vectorizable discrete random-sampling methods, along with the commonly used inverse sampling method, is assessed on a vector machine. Monte Carlo applications involving, one-dimensional, two-dimensional and multi-dimensional probability tables are used in the investigation. Various forms of the weighted sampling method and methods that transform the original probability table are examined. It is found that some form of weighted sampling is efficient, when the original probability distribution is not far from uniform or can be approximated analytically. Table transformation methods, though requiring additional memory storage, are best suited in applications where multidimensional tables are involved.