摘要:

A fine grain mapping strategy for multiprocessor systems especially suitable for RISC and VLIW type MIMD computers is described. The objective of the strategy is to minimise the total execution time of the application algorithms that are to be executed on the target systems. An application algorithm which has been coded as a straight line program is compiled to generate intermediate codes. This code is then represented by a data dependence graph. A node in the graph corresponds to the operation of one intermediate code statement, and arcs between nodes represent the data dependence between operations. The mapping strategy, called SR-mapper, is a generalised list scheduler. When SR-mapper does the mapping procedure, the data dependence between nodes, the pipeline effect of each processing element within the system, and the communication cost between processing elements are considered. SR-mapper uses slot reservation technique to insert send nodes for the immediate successor nodes when a node has been scheduled to maintain the data dependence between nodes and to achieve the synchronisation between processing elements. SR-mapper has been implemented and several scientific application algorithms, such as matrix multiplication, L-U decomposition, weighted median filter, convolution kernel etc. have been used as the testing inputs. Results show that on the average the speedup obtained by SR-mapper is 4.480 times as large as the one obtained by the mapper which does not employ the pipeline effect assuming the weight of operations are 4 for addition and subtraction and 6 for multiplication and division. During the mapping phase, if the slot reservation technique is adopted, the gain of speedup is 21%, on the average, more than the one obtained by the mapper which does not apply the slot reservation technique. If all nodes have an equal weight of 1, the average efficiency of the systems with the number of processing elements ranging from 2 to 32 and communication costs ranging from 0 to 20 is 0.481. These results are encouraging.

DOI:10.1049/ip-e.1991.0015

出版商:IEE    

年代:1991

数据来源: IET

摘要:

A popular form of random-number generator uses the recurrencesk= (ASk−1mod 2ewithAands0odd to produce a pseudo-random sequence of integers in the range 0 to 2e− 1. We give a simple modification which increases the guaranteed period by an enormous factor with only a small computational overhead. The recurrence is changed tosk= (Ask−1+ Sk−nmod 2ewherenis such thatxn+ x + 1 is a primitive binary polynomial. The period is increased from 2e−2to (2n−1)2e−1. The overhead is an extra addition and the inclusion of a circular buffer of lengthn.

DOI:10.1049/ip-e.1991.0016

出版商:IEE    

年代:1991

数据来源: IET

摘要:

We analyse the performance of a multistage interconnection network (MIN) with a packet-switching protocol, embedded in a closed network of processors. First, the expected value of transmission time through a delta-2 type of MIN is determined. We then obtain, for the first time by an analytical method, a formula for its probability density function from which the variance and higher moments follow. Previously densities have only been estimated by simulation which is expensive and can be unreliable, especially in the often crucial tail region. Numerical results reveal new insights into the hot-spot phenomenon which occurs when one output address is selected more frequently than the others. We first show how mean transmission time on hot paths increases with the hot-spot intensity and compare this with cooler paths. We also plot the density functions for these transmission times. Hence it is possible to determine precisely transmission time variability and to obtain reliability measures from their tails. The approach can handle arbitrary routing frequencies to the MIN output addresses and suggests new approximation techniques with wider applicability.

DOI:10.1049/ip-e.1991.0017

出版商:IEE    

年代:1991

数据来源: IET

摘要:

A new approach for reconfiguring multipipeline arrays from two-dimensional arrays is analysed. The proposed reconfiguration approach is fully characterised and the conditions for switching and routing are given. A polynomial time complexity algorithm is proposed for the reconfiguration of multipipeline arrays. This algorithm is based on a novel divide-and-conquer technique; this technique is based on a heuristic condition for dividing an array into multiple sub-arrays. This results in a lower internal delay. This condition also achieves lower values for average intercell and pipeline delays than previous approaches. It is proved that using the proposed algorithm, maximum multipipeline generation is possible. A switching arrangement consisting of two buses per channel is required.

DOI:10.1049/ip-e.1991.0018

出版商:IEE    

年代:1991

数据来源: IET

摘要:

A fast Tausworthe-type random number generator has been implemented as a VLSI circuit on silicon for Monte-Carlo simulation purposes in a parallel multiprocessor system environment. The generator, which has uniform distribution, has been contructed for use as a peripheral device to be connected with each processor unit. General considerations for parallel random number generation are discussed and desirable properties are reviewed as a starting point for a VLSI implementation. The hardware design is based on the maximal length shift register sequences. It involves concurrent architecture in which a single shift operation is equivalent to 16 shifts in the original shift register unit. A new 16-bit random number is generated during each shifting operation. The chip is fully microprocessor bus compatible with a 16-bit bidirectional data bus and three I/O control lines. The methods of shift register sequence segmentation are also reviewed. Practical aspects for parallel processing system purposes are given. The generator has been submitted to a comprehensive set of statistical tests.

DOI:10.1049/ip-e.1991.0019

出版商:IEE    

年代:1991

数据来源: IET

摘要:

The fast Tamari transform (FTT), which is suitable to obtain some properties ofp-valued digital functions and networks (pbeing the power of a prime) is presented. A systematic procedure to calculate the FTT is defined, and an expression for the complexity of calculation, and flow-graphs and networks for the calculation of the FTT are also presented. All aspects are illustrated with several examples.

DOI:10.1049/ip-e.1991.0020

出版商:IEE    

年代:1991

数据来源: IET

摘要:

Two techniques are proposed which enhance the optimisation efficiency of CMOS combinational logic circuits. One uses transition times (rise and fall times) of each gate as variables of the optimisation process. The other technique uses the optimal characteristic waveform synthesising method (OCWSM) to obtain the initial guess for the optimisation process. The optimisation process, with these two techniques, can perform sizing and optimisation for circuits with a smaller fixed-delay specification than other sizing and optimisation algorithms. The circuits sized using the proposed algorithm have shown a smaller power dissipation, especially when the delay specification is small. The CPU time consumed is reasonable. High-speed low-power circuits are thus more realisable using the proposed algorithm.

DOI:10.1049/ip-e.1991.0021

出版商:IEE    

年代:1991

数据来源: IET

摘要:

A remote password authentication scheme based on the Chinese remainder theorem is proposed. The scheme can verify the remote password without verification tables. In the initial phase, the password generation centre generates and assigns a password corresponding to each user. The ideas of smart cards and the identity-based signature scheme introduced by Shamir are employed in this phase. Each user possesses a smart card for later login and authentication. In the login phase, the user submits the identity and password associated with the smart card. In the authentication phase, the system verifies the remotely submitted password to check if the login request is accepted or rejected. A signature scheme and communication timestamps are provided in the authentication phase against the potential attacks of replaying a previously intercepted login request.

DOI:10.1049/ip-e.1991.0022

出版商:IEE    

年代:1991

数据来源: IET