Home
>
Journals & magazines
>
IEE Proceedings - Computers and Digital Technique...
>
Volume 143
Issue 4
IEE Proceedings - Computers and Digital Techniques
Volume 143, Issue 4, July 1996
Volumes & issues:
Volume 143, Issue 4
July 1996
-
- Author(s): A.E.A. Almaini and L. McKenzie
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 4, p. 205 –212
- DOI: 10.1049/ip-cdt:19960564
- Type: Article
- + Show details - Hide details
-
p.
205
–212
(8)
Tabular techniques and algorithms for generating Kronecker expansions are presented. The Kronecker expansions, a subclass of mixed-polarity Reed–Muller expansions, can be generated from Boolean functions or from Kronecker expansions of different polarity. The techniques can be used for completely and incompletely specified Boolean functions. The algorithms were implemented in Pascal and fully tested. Examples are given to illustrate the procedures. - Author(s): G.R. Higgie
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 4, p. 213 –218
- DOI: 10.1049/ip-cdt:19960426
- Type: Article
- + Show details - Hide details
-
p.
213
–218
(6)
T-codes are variable-length codes that have been shown to provide excellent codeword synchronisation properties without any sacrifice in coding efficiency. Previously published results have used simulation techniques to ascertain the synchronising properties of each T-code. The author presents the first theoretical technique for calculating the synchronising delay of a T-code based on the code set's construction. The development of a database of best T-codes from which an optimally efficient code with superb synchronising properties can be easily chosen is also documented. - Author(s): K.L. Wong and A.G. Constantinides
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 4, p. 219 –223
- DOI: 10.1049/ip-cdt:19960469
- Type: Article
- + Show details - Hide details
-
p.
219
–223
(5)
In the paper, a novel problem-independent parallel realisation of the simulated annealing (SA) algorithm is proposed. By employing speculative computation, concurrency is introduced into the inherently sequential algorithm. This is achieved by predicting the acceptance of each generated move before the move is evaluated. Based on this prediction, subsequent moves can be proposed and evaluated before decisions on whether to accept or reject preceeding moves are made. To preserve the sequential decision nature of SA, all moves subsequent to a prediction that is eventually proved wrong are discarded. A simple and effective prediction mechanism using previous move statistics is developed. Efficient realisation of the parallel SA algorithm on a ring multiprocessor architecture is described. Analytical and simulation performance results are presented. These results indicate that the authors' parallel SA is best implemented on a coarse to medium grain multiprocessor system. Factors affecting performance in actual implementations are also discussed. - Author(s): R.-Y. Hwang
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 4, p. 224 –231
- DOI: 10.1049/ip-cdt:19960358
- Type: Article
- + Show details - Hide details
-
p.
224
–231
(8)
A statement-level migration of synchronisation operation for performance enhancement is proposed. Theorems show that system performance is enhanced if the number of array elements in the maximal backward synchronisation region is reduced. This task is divided into three steps. First the redundant statements are moved out of the maximal backward synchronisation region by dependence analysis. Secondly, these two statements, which consist of a dependence source and its corresponding sink, respectively, are rewritten to reduce the range of the maximal backward synchronisation region. Finally, the redundant array elements are moved out of the maximal backward synchronisation region. Nine perfect benchmarks are employed to evaluate the performance enhancement after migration. Experimental results show that the enhancement is very significant. - Author(s): G. Panneerselvam ; S. Bandyopadhyay ; G.A. Jullien
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 4, p. 232 –238
- DOI: 10.1049/ip-cdt:19960489
- Type: Article
- + Show details - Hide details
-
p.
232
–238
(7)
Area efficient VLSI design of interconnection networks is an important problem in multiprocessor design. In the context of ULSI technology, the delay in signal propagation along wires will become a significant limitation in designing large, fast networks. This limitation is particularly applicable for high wire organisations typically used in interconnection networks. In the paper, it is shown that classical cross-bar type interconnection networks, formed as systolic arrays, have better composite VLSI performance metrics than most popular interconnection networks that use high wire organisations even though systolic organisations have the disadvantage of being larger in terms of silicon area. The authors outline a new, hybrid architecture for interconnection networks that trades speed advantages of systolic arrays with area advantages of high wire organisations. An implementation, in VLSI, of a butterfly network using the proposed approach is described, and it is shown why this is useful in designing an area efficient interconnection network. - Author(s): A. Symons and V. Lakshmi Narasimhan
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 4, p. 239 –245
- DOI: 10.1049/ip-cdt:19960467
- Type: Article
- + Show details - Hide details
-
p.
239
–245
(7)
The maximum speedup of a multiprocessor system is limited by the sequential part of an algorithm, and in loosely coupled processor systems a large part of this sequentiality is caused by the communication between processors. As this communication is dependent on the distribution of data the data distribution must be optimised in order to achieve the maximum speedup. In the paper the authors present a new method of determining the distribution for loosely coupled multiprocessors using a branch and bound technique based on the Moore-Skelboe interval arithmetic algorithm. The key issue of this load–balancing algorithm has been addressed, namely the branch selection criterion. When this method is applied to a matrix multiplication algorithm running on a cluster of workstations, the optimal data distribution provides a significant performance increase of 44% over the equal distribution, which does not take into account communication overheads. Further, it is shown that, for a workstation cluster with random variations in their processing speeds, the execution time ratio of the equal and optimal distributions remains relatively unchanged. Thus the execution time of the optimal data distribution is no more sensitive to processor speed variation than the execution time of the equal distribution. - Author(s): L.-P. Ku and H.W. Leong
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 143, Issue 4, p. 246 –248
- DOI: 10.1049/ip-cdt:19960563
- Type: Article
- + Show details - Hide details
-
p.
246
–248
(3)
An OTP algorithm for solving the optimal tile-partitioning problem has recently been published. The OTP algorithm makes use of an elimination algorithm to find a maximum set of nonintersecting critical partition edges. It is shown that this elimination algorithm is flawed.
Tabular techniques for generating Kronecker expansions
Database of best T-codes
Speculative parallel simulated annealing with acceptance prediction
Performance-oriented synchronisation migration in a Doacross loop
Area efficient systolic interconnection networks
Development of a method of optimising data distribution on a loosely coupled multiprocessor system
Note on optimal tile partition for space region of integrated-circuit geometry
Most viewed content for this Journal
Article
content/journals/ip-cdt
Journal
5
Most cited content for this Journal
We currently have no most cited data available for this content.