In this paper, we propose an adaptive parallel grouping algorithm that may reduce the number of collisions and increase overall throughout of B-WLL MAC protocol. Also, we present a method for independently executing t...
详细信息
In this paper, we propose an adaptive parallel grouping algorithm that may reduce the number of collisions and increase overall throughout of B-WLL MAC protocol. Also, we present a method for independently executing the adaptive parallel grouping algorithm to reduce the signaling traffic overheads.
The Bulk Communication Scheduling Heuristic (BCSH) task scheduling algorithm is proposed. By generating only bulk synchronous style schedules, BCSH reduces some software overheads of messages from a source processor t...
详细信息
The Bulk Communication Scheduling Heuristic (BCSH) task scheduling algorithm is proposed. By generating only bulk synchronous style schedules, BCSH reduces some software overheads of messages from a source processor to the same destination processor to almost one software overhead, and thus improves the performance of a parallel program significantly. Further, some performance comparisons between BCSH and Kruatrachue's algorithm DSH are discussed.
This paper briefly reviews some of the more popular parallel computer models - pipelined optical bus and OTIS (optical transpose interconnect system) models - that employ optical interconnects. The interconnect topolo...
详细信息
This paper briefly reviews some of the more popular parallel computer models - pipelined optical bus and OTIS (optical transpose interconnect system) models - that employ optical interconnects. The interconnect topology and some simple algorithms for each model are also described.
It has been proved that incomplete binary trees can not be embedded onto incomplete hypercubes with both expansion-1 and dilation-1. In this paper, we propose an optimal embedding algorithm to embed this issue with ex...
详细信息
It has been proved that incomplete binary trees can not be embedded onto incomplete hypercubes with both expansion-1 and dilation-1. In this paper, we propose an optimal embedding algorithm to embed this issue with expansion-1, dilation-2. Our algorithm is a linear time algorithm, which is optimal in terms of time complexity. Furthermore, the embedding scheme is as desirable to be simple such that the implementation is quite easy.
Massively parallel computers consisting of a large number of processing elements have been developed and expected as high performance computers in advanced science and technology. Practical parallel computation model ...
详细信息
Massively parallel computers consisting of a large number of processing elements have been developed and expected as high performance computers in advanced science and technology. Practical parallel computation model has been required to analyze parallel algorithms on massively parallel computers. We present a practical parallel computation model LogPQ taking account of communication queues into the LogP model. The LogPQ model has three queues for each communication line, and four supplement parameters in addition to the LogP model. This paper addresses the performance of parallel matrix multiplication using the LogPQ model. The parallel performances on the parallel machine CM-5 are compared between the LogP and LogPQ model. It is seen that the LogPQ model expects the execution times more accurately than the LogP model.
Mobile agent has been shown to be a convenient, efficient, and robust approach to designing distributed protocols. This paper introduces an adaptive, mobile-agents-based routing algorithm. While performing a random wa...
详细信息
Mobile agent has been shown to be a convenient, efficient, and robust approach to designing distributed protocols. This paper introduces an adaptive, mobile-agents-based routing algorithm. While performing a random walk through the network, mobile agents sense changes in network state, and trigger the computation of updated values for the routing tables. The randomized moving strategy exerts a negligible and balanced impact on the network resources, both in terms of bandwidth and computation. The memory requirement is very moderate. The correctness of the protocol is proven and its complexity is analyzed.
In this paper, I describe a simple functional programming language, GRL, in which most of the characteristic features of the popular behavior-based robot architectures can be concisely written as reusable software abs...
详细信息
Constrained reconfigurable meshes are one type of parallel computing model which takes the reconfigurability of hardware into account. With these meshes, a practical assumption is given on the communication power such...
详细信息
Constrained reconfigurable meshes are one type of parallel computing model which takes the reconfigurability of hardware into account. With these meshes, a practical assumption is given on the communication power such that a signal is propagated through a constant number of processing elements (PEs), say k PEs, at one unit of time. In this paper, we present algorithms for the fundamental problem of computing the sum of multiple integers. For the problem of summing n binary values, we show an optimal O(n/k)-time algorithm on a constrained reconfigurable mesh of size m × n, where m = Θ (log2 k/log log k). For the problem of summing n d-bit integers, we present an O((d + √dmm)/k)-time algorithm on a constrained reconfigurable mesh of size √ dmn × √ dmn.
In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n × n binary image on the Bulk-Synchronous parallel(BSP) model. The first algorithm is for weighted distance, and th...
详细信息
In this paper, we present two parallel algorithms for computing the all nearest neighbors of an n × n binary image on the Bulk-Synchronous parallel(BSP) model. The first algorithm is for weighted distance, and the second algorithm is for Lp distance. Both two algorithms run in O(n2/p + L) computation time and O(g n/√p + L) communication time using p (1 &le p &le n) processors and in O(n2/p + (d + L)log p/n/log(d + l)) computation time and in O(g n/√p + (gd + L)log p/n/log(d + l)) communication time using p (n 2) processors, for any integer d (1 &le d &le p/n), where L denotes synchronization periodicity and g denotes a reciprocal of communication bandwidth.
Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops which have a re...
详细信息
Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops which have a regular stencil of data dependences. Tiling is a well-known optimization that improves performance on such loops, particularly for computers with a multi-levelled hierarchy of parallelism and memory. Most previous work on tiling restricts the tile shape to be rectangular. Our previous work and its extension by Desprez, Dongarra, Rastello and Robert showed that for doubly nested loops, using parallelograms can improve parallel execution time by decreasing the idle time, the time that a processor spends waiting for data or synchronization. In this paper, we extend that work to more deeply nested loops, as well as to more complex loop bounds. We introduce a model which allows us to demonstrate the equivalence in complexity of linear programming and determining the execution time of a tiling in the model. We then identify a sub-class of these loops that constitute rectilinear iteration spaces for which we derive a closed form formula for their execution time. This formula can be used by a compiler to predict the execution time of a loop nest. We then derive the tile shape that minimizes this formula. Using the duality property of linear programming, we also study how the longest path of dependent tiles within a rectilinear iteration space changes with the tile shape. Finally, we observe that the execution time of a rectilinear iteration space depends on the slope of only four of the facets defining the iteration space, independent of its dimensionality.
暂无评论