Narrow Results

Many HPC systems run workloads comprising scientific simulations where the problem size is often fixed while model parameters are changed for each run. The speedup profile of such applications can often be determined using data from previous runs. Many applications exhibit sublinear speedups and thus only incremental improvements in execution time when larger numbers of processors are used. In this paper, we consider a workload of applications queued for execution and co-schedules that can exploit speedup profiles. More specifically, we seek co-schedules to reduce workload completion time (i.e., makespan), and total energy consumed by the system. Additionally, we explore how co-schedules may reduce average application turnaround time and thus benefit the user. We propose speedup-aware processor partitioning (SAPP) co-scheduling schemes, including optimal and greedy variants. We show that our greedy co-schedules reduce system energy, workload makespan and average application turnaround time when compared to a base scheme that runs each application on all available processors. Our experiments demonstrate that on a system with 128 processors, on average, our SAPP-greedy co-schedules can reduce makespan and turnaround time by 20% and decrease total energy consumed by 40%.

A simple means of integrating the characteristics of networked processors under divisible loads into Amdahl’s Law is presented. Amdahl’s Law serves as an upper bound to these speedup results. Amdahl’s Law with divisible load processing characteristics included serves as an upper bound to speedup for any model taking into consideration more detailed peculiarities of real systems such as the overhead of task creation, synchronization, resource contention and memory issues.

The conventional form of Amdahl’s law states that speedup of calculations in a multiprocessor machine is limited by the definite constant value just due to the existence of some non-parallelizable part in any algorithm. This brief paper considers one more general reason, which prevents a growth of parallel performance: processes that implement distributed task cannot start simultaneously and hence every process adds some start-up time, also reducing by that the gain from a parallel processing. The simple formula, proposed here to extend Amdahl’s law, leads to a less optimistic picture in comparison with classical results: for large amount of processor units the modified law does not approach to constant but vanishes. This is the result of competition between two factors: decreasing of calculation duty and increasing of start-up time when a number of parallel processes grows. The effect may be subdued by means of specific regularity in launching parallel processes.

Traditionally, interest in parallel computation centered around the speedup provided by parallel algorithms over their sequential counterparts. In this paper, we ask a different type of question: Can parallel computers, due to their speed, do more than simply speed up the solution to a problem? We show that for real-time optimization problems, a parallel computer can obtain a solution that is better than that obtained by a sequential one. Specifically, a sequential and a parallel algorithm are exhibited for the problem of computing the best-possible approximation to the minimum-weight spanning tree of a connected, undirected and weighted graph whose vertices and edges are not all available at the outset, but instead arrive in real time. While the parallel algorithm succeeds in computing the exact minimum-weight spanning tree, the sequential algorithm can only manage to obtain an approximate solution. In the worst case, the ratio of the weight of the solution obtained sequentially to that of the solution computed in parallel can be arbitrarily large.

In this paper, a parallel Eulerian hydrocode for the simulation of large scale complicated explosion and impact problem is developed. The data dependency in the parallel algorithm is studied in particular. As a test, the three dimensional numerical simulation of the explosion field in an unlimited atmosphere is performed. The numerical results are in good agreement with the empirical results, indicating that the proposed parallel algorithm in this paper is valid. Finally, the parallel speedup and parallel efficiency under different dividing domain areas are analyzed.

This paper describes the parallel implementation of the Z-Buffer algorithm on a distributed memory machine. The Z-Buffer is one of the most popular techniques used to generate a representation of a scene consisting of objects in a three-dimensional world. We propose and compare two different parallel implementations on a reconfigurable network of Transputers. In the first approach, the description of the scene is distributed among the processors configured as a tree. The picture is processed in a pipelined fashion, in order to output parts of the image during the computation of the remainder. We show the influence of the degree and the height of the tree on the global performance of the algorithm. In a second approach, both the picture and the scene description are distributed to the processors. We have therefore to redistribute dynamically the tiles among the processors at the beginning of the computation. To perform this redistribution, a special algorithm is designed for the case where the processors are configured as a unidirectional or bidirectional ring. Then we implement a greedy algorithm that enables us to perform the redistribution on an arbitrary interconnection network. We show that the two approaches are complementary: for small pictures or large scenes, a tree-based algorithm performs better than a redistribution-based algorithm, but for large pictures or smaller scenes, it is the other way round. We obtain substantial speedups over the sequential implementation, with up to 32 processors.

Many researchers have pointed out that using complex scheduling algorithms in input queuing switches with virtual output queuing (VOQ) scheme can achieve 100% throughput. But these algorithms are too complex to be implemented in hardware. In this paper, based on combined input/output queuing (CIOQ) switch fabrics, we propose a simple scheduling algorithm named outlet priority round robin (OPRR). For synthetic workloads we consider, including uniform and bursty traffic models, the performance of OPRR in VOQ mode and single queue mode is evaluated respectively. Through the simulation results we show that 1) OPRR algorithm, coupled with the speedup of 2, can lead to performance very close to output queuing switches, and 2) under the same condition, OPRR algorithm in single queue mode behaves almost identically to VOQ mode. These results are very useful to direct the design and implementation of switch fabrics in core routers.

This paper describes the parallel implementation of the Z-Buffer algorithm on a distributed memory machine. The Z-Buffer is one of the most popular techniques used to generate a representation of a scene consisting of objects in a three-dimensional world. We propose and compare two different parallel implementations on a reconfigurable network of Transputers. In the first approach, the description of the scene is distributed among the processors configured as a tree. The picture is processed in a pipelined fashion, in order to output parts of the image during the computation of the remainder. We show the influence of the degree and the height of the tree on the global performance of the algorithm. In a second approach, both the picture and the scene description are distributed to the processors. We have therefore to redistribute dynamically the tiles among the processors at the beginning of the computation. To perform this redistribution, a special algorithm is designed for the case where the processors are configured as a unidirectional or bidirectional ring. Then we implement a greedy algorithm that enables us to perform the redistribution on an arbitrary interconnection network. We show that the two approaches are complementary: for small pictures or large scenes, a tree-based algorithm performs better than a redistribution-based algorithm, but for large pictures or smaller scenes, it is the other way round. We obtain substantial speedups over the sequential implementation, with up to 32 processors.