Narrow Results

We investigate the average-case speed and scalability of parallel algorithms executing on multiprocessors. Our performance metrics are average-speed and isospeed scalability. For the purpose of average-case performance prediction, we formally define the concepts of average-case average-speed and average-case isospeed scalability. By modeling parallel algorithms on multiprocessors using task precedence graphs, we are mainly interested in the effects of synchronization overhead and load imbalance on the performance of parallel computations. Thus, we focus on the structures of parallel computations, whose inherent sequential parts are limitations to high performance. Task execution times are treated as random variables, so that we can analyze the average-case performance of parallel computations. For several typical classes of task graphs, including iterative computations, search trees, partitioning algorithms, and diamond dags, we derive the growth rate of the number of tasks as well as isospeed scalability in keeping constant average-speed. In addition to analytical results, extensive numerical data are also demonstrated. An important discovery of our study is that while a parallel computation can be made scalable by increasing the problem size together with the system size, it is actually the amount of parallelism that should scale up with the system size. We also argue that under our probabilistic model of parallel algorithms and the list scheduling strategy, the number of tasks should grow at least at the rate of Θ(P log P), where P is the number of processors, so that a constant average-speed can be maintained. Furthermore, Θ(log P/ log P') is the highest isospeed scalability achievable.

The demand for high-performance supercomputers has been growing rapidly in the scientific and engineering fields. To meet this demand, Fujitsu has developed new pipelined supercomputers, the VP2000 series, which attain a maximum performance of up to 5 GFLOPS. This paper describes the VP2000 series in the following areas: architecture, hardware features, hardware technology, multiprocessor system, and software features.

The primary goal of processor scheduling is to assign tasks in a parallel program to processors, so as to minimize the execution time. Most existing approaches to processor scheduling for multiprocessors assume that the execution time of each task is fixed and is independent of processor scheduling. In this paper, we argue that the execution time of a given task is not fixed but is critically dependent on the performance of the caches, which have become an essential component of shared-memory multiprocessors and propose a scheduling algorithm, called data distribution constrained scheduling algorithm. The proposed scheduling algorithm tries to maximize the number of cache hits by scheduling the processors so that the task that brings a memory block into the cache and the tasks that subsequently access the same memory block are executed on the same processor.

In this paper, we develop four numerical methods for computing the singular value decomposition (SVD) of large sparse matrices on a shared-memory multiprocessor architecture. We particularly consider the SVD of unstructured sparse matrices in which the number of rows may be substantially larger or smaller than the number of columns. We emphasize Lanczos, block-Lanczos, subspace iteration and the trace minimization methods for determining a select number of smallest singular triplets (singular values and corresponding left- and right-singular vectors) for sparse matrices. The target architectures for implementations of such methods include the Alliant FX/80 and the Cray-2S/4–128. This algorithmic research is particularly motivated by recent information-retrieval techniques in which approximations to large sparse term-document matrices are needed, and by nonlinear inverse problems arising from seismic reflection tomography applications.

In this paper, we consider the problem of solving tridiagonal linear systems on distributed-memory multiprocessors. We present a new parallel partition-based tridiagonal solver that is suitable for such parallel computers. As compared with the well representative algorithm-cyclic reduction and its parallel variant-cyclic elimination, our algorithm exploits sufficient high of parallelism throughout without incurring more data traffic.

We consider the practical performance of dynamic task distribution on a multiprocessor, where overloaded processors dispense tasks to be performed on idle ones which are free to execute them. We propose a topology and an algorithm for routing packets in a network from an arbitrary subset of processors S to an arbitrary subset T, where the exact target node within T for a particular task is unimportant and therefore not specified.

The method presented achieves work distribution in O(10* log N) time, where N is the nodes (processors) number. It operates on a Duplex Butterfly, and requires O(log N) size buffers. The solution is dynamic, taking into consideration real time availability of processors, and deterministic. The mechanism includes throttling of the task generation rate. “Software synchronization” in asynchronous mode ensures the insensitivity of the algorithm to hardware propagation delays of signals in large networks.

Processor allocation is an important issue for efficient utilization of a multiprocessor system. Several well-known methods exist for processor allocation in the hypercube multiprocessor. Some disadvantages of the hypercube structure have been overcome in the Extended Hypercube. The paper attempts at showing how the processor allocation schemes of hypercube can be extended to the Extended Hypercube structure. Results of a simulation study are also provided.

In this paper, we propose a new parallel bidirectional algorithm, based on Cholesky factorization, for the solution of sparse symmetric system of linear equations. Unlike the existing algorithms, the numerical factorization phase of our algorithm is carried out in such a manner that the entire back substitution component of the substitution phase is replaced by a single step division. Since there is a substantial reduction in the time taken by the repeated execution of the substitution phase, our algorithm is particularly suited for the solution of systems with multiple b-vectors. The effectiveness of our algorithm is demonstrated by comparing it with the existing parallel algorithm, based on Cholesky factorization, using extensive simulation studies on two-dimensional problems discretized by FEM.

In Part I of this paper, we proposed a new parallel bidirectional algorithm, based on Cholesky factorization, for the solution of sparse symmetric system of linear equations. In this paper, we propose a new parallel bidirectional algorithm, based on LU factorization, for the solution of general sparse system of linear equations having non symmetric coefficient matrix. As with the sparse symmetric systems, the numerical factorization phase of our algorithm is carried out in such a manner that the entire back substitution component of the substitution phase is replaced by a single step division. However, due to absence of symmetry, important differences arise in the ordering technique, the symbolic factorization phase, and message passing during numerical factorization phase. The bidirectional substitution phase for solving general sparse systems is the same as that for sparse symmetric systems. The effectiveness of our algorithm is demonstrated by comparing it with the existing parallel algorithm, based on LU factorization, using extensive simulation studies.

In this paper, we propose a hardware-centric memory consistency model particularly for shared-memory multiprocessors with parallel-multithreaded processing elements. According to the behavior of critical sections and the feature of parallel-multithreaded processors, we extend the release consistency model to a more relaxed memory model. A release reference at the end of a critical section can be executed locally regardless of whether all of its previous ordinary references have performed. The requirement is that another thread on the same processor is waiting for the lock to be freed. Two new instructions and two additional macros are needed to properly label a program for our proposed model. Moreover, we use a table per processing element to determine if there are any threads waiting for a specific lock. We have used five benchmark programs in the SPLASH suite to evaluate the performance gain for the new model. According to the simulation results, our proposed model is superior to the release consistency model up to 25%.

The problem of nonpreemptively scheduling a set of n independent jobs with identical release times so as to minimize the number of late jobs is considered. It is known that the problem can be solved in O(n log n) time, by an algorithm due to Moore, for a single processor, and that it becomes NP-hard for two or more identical processors, even if all jobs have identical due dates. In this paper we give a fast heuristic, based on Moore’s algorithm, for the multiprocessor case. Like Moore’s algorithm, our heuristic also admits an O(n log n) implementation. It is shown that the performance ratio of the heuristic is 4/3 for two identical processors, where the performance ratio is defined to be the least upper bound of the ratio of the number of on-time jobs in an optimal schedule versus that in the schedule generated by the heuristic.

With the recent increase in IP traffic owing to fiber communication, previous schemes have become inadequate for link-layer processing of IP over SONET/SDH(POS). In this study, a proposal based on $m$ processors to provide mapping or demapping of IP datagrams from or into SONET/SDH is presented, and the value of $m$ is decided based on the link layer rate of POS. Further, the mathematic model of proposed architecture are presented in detail. Then the realization procedures are implemented in a Field-Programmable Gate Array (FPGA). Both theoretical analysis and experimental test prove that the proposed scheme is efficient, portable, cost-efficient and has a lower hardware resources consumption.

A modification is proposed to the Safe Point Thinning Algorithm (SPTA) to speed it up. The modified algorithm was implemented on a single processor. It was then implemented on the Homogeneous Multiprocessor Proper under two techniques: data decomposition and function decomposition. Experimental results show that with our modification and multiprocessor implementations, the SPTA was considerably speeded up.

An approach for designing a hybrid parallel system that can perform different levels of parallelism adaptively is presented. An adaptive parallel computer vision system (APVIS) is proposed to attain this goal. The APVIS is constructed by integrating two different types of parallel architectures, i.e. a multiprocessor based system (MBS) and a memory based processor array (MPA), tightly into a single machine. One important feature in the APVIS is that the programming interface to execute data parallel code onto the MPA is the same as the usual subroutine calling mechanism. Thus the existence of the MPA is transparent to the programmers. This research is to design an underlying base architecture that can be optimally executed for a broad range of vision tasks. A performance model is provided to show the effectiveness of the APVIS. It turns out that the proposed APVIS can provide significant performance improvement and cost effectiveness for highly parallel applications having a mixed set of parallelisms. Also an example application composed of a series of vision algorithms, from low-level and medium-level processing steps, is mapped onto the MPA. Consequently, the APVIS with a few or tens of MPA modules can perform the chosen example application in real time when multiple images are incoming successively with a few seconds inter-arrival time.

In scalable CC-NUMA multiprocessors, it is crucial to reduce the average memory access time. For applications where the second-level (L2) cache is large enough, we propose a split L2 cache to utilize the surplus space. The split L2 cache is composed of a traditional LRU cache and an RVC (Remote Victim Cache) which only stores the data of remote memory address range. Thus, it reduces the average L2 cache miss time by keeping remote blocks that would be discarded otherwise. Though the split cache does not reduce the miss rates, it is observed to reduce the total execution time effectively by up to 27%.It even outperform an LRU cache of double size.

In the field of real-time multiprocessor scheduling, researchers have found that global scheduling on average results in better resource utilization than partitioned scheduling, and is more robust in the presence of timing errors. In this paper, we present a global scheduling algorithm JPA with Job-level Priority Assignment for sporadic task systems that can be viewed as a generalization of both FPS and EDF. We also introduce JPA's efficient variant, which greatly reduces the runtime overhead comparing with JPA. As will be shown by the experiments, JPA indeed exhibits much better performance than the state-of-the-art multiprocessor scheduling/analysis techniques based on FPS and EDF.

We investigate the average-case scalability of parallel algorithms executing on multicomputer systems whose static networks are k-ary d-cubes. Our performance metrics are isoefficiency function and isospeed scalability. For the purpose of average-case performance analysis, we formally define the concepts of average-case isoefficiency function and average-case isospeed scalability. By modeling parallel algorithms on multicomputers using task interaction graphs, we are mainly interested in the effects of communication overhead and load imbalance on the performance of parallel computations. We focus on the topology of static networks whose limited connectivities are constraints to high performance. In our probabilistic model, task computation and communication times are treated as random variables, so that we can analyze the average-case performance of parallel computations. We derive the expected parallel execution time on symmetric static networks and apply the result to k-ary d-cubes. We characterize the maximum tolerable communication overhead such that constant average-case efficiency and average-case average-speed could be maintained and that the number of tasks has a growth rate Θ(P log P), where P is the number of processors. It is found that the scalability of a parallel computation is essentially determined by the topology of a static network, i.e., the architecture of a parallel computer system. We also argue that under our probabilistic model, the number of tasks should grow at least in the rate of Θ(P log P), so that constant average-case efficiency and average-speed can be maintained.

The performance of the Simple List Scheduling algorithm is unsatisfactory. In order to get the better schedule solution, this paper designs a novel task scheduling algorithm which is named as the Iterative List Scheduling algorithm. Compared with the Simple List Scheduling algorithm, the Iterative List Scheduling algorithm enlarges the search space of graph topological order to get smaller schedule length. Experiments with different scale of macroblock and different communication cost are provided to compare the performance of the Iterative List Scheduling and that of the Simple List Scheduling algorithm. Comparison result indicates that, the Iterative List Scheduling algorithm can schedule tasks more effectively than the Simple List Scheduling algorithm, especially under the circumstance of high communication cost. The maximum accelerate ratio reaches 102.8%