Home
>
Journals & magazines
>
IEE Proceedings - Computers and Digital Technique...
>
Volume 141
Issue 4
IEE Proceedings - Computers and Digital Techniques
Volume 141, Issue 4, July 1994
Volumes & issues:
Volume 141, Issue 4
July 1994
-
- Author(s): C.-C. Hsu and Y.-W. Liu
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 4, p. 205 –211
- DOI: 10.1049/ip-cdt:19941150
- Type: Article
- + Show details - Hide details
-
p.
205
–211
(7)
The authors propose a novel approach for embedding a (d-1) level and a (d-2) level complete binary tree (CBT) into a d-dimensional hypercube (d-cube). Moreover, free processors are used as spare processors to recover a single fault in the two trees. The primary results are that the (d-1)-CBT can be recovered in at most two steps and the (d-2)-CBT in one step. The dilation of the recovered embedding is at most two and the processor utilisation is near 75%. - Author(s): E. Walker and G. Morgan
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 4, p. 212 –220
- DOI: 10.1049/ip-cdt:19941229
- Type: Article
- + Show details - Hide details
-
p.
212
–220
(9)
Reports on the progress of the prototyping of a novel iterative structure solver: the York Stream Machine. The York Stream Machine has a pipeline ring data-flow architecture. The processing elements in the architecture are FPGA (field programmable gate array) devices which are capable of implementing directly many register or combinatorial functions. The authors highlight: (i) the network topology, (ii) the processing element architecture, (iii) the microinstruction generation techniques and (iv) the method employed by the Stream Machine to solve iterative algorithms. The StreamTalk compiler developed to support the Stream Machine is also described. The StreamTalk compiler takes as input a nested loop program expressed in an imperative syntax. It then constructs an intermediate task graph representation of its computation and maps the computation onto the pipeline ring structure. Encouraging speedups are demonstrated when the compiler is applied to some common nested loop kernels. The long term objective of the Stream Machine project is to demonstrate that by parallelising iterations in an algorithm over a pipeline ring and using hardware accelerating devices like FPGAs as processing elements, very high performances can be achieved. - Author(s): M.J. Avedillo ; J.M. Quintana ; J.L. Huertas
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 4, p. 221 –228
- DOI: 10.1049/ip-cdt:19941151
- Type: Article
- + Show details - Hide details
-
p.
221
–228
(8)
A new hardware scheme for easily testable PLA-based finite state-machines is proposed. With this scheme, all combinationally nonredundant crosspoint faults in the PLA logic implementation are testable. Moreover, test generation is easily accomplished because short systematic initialisation sequences exist for each internal state in the machine and unit length distinguishing sequences, which hold under the faulty condition existing for every true faulty state pair. The authors present an outline of the proposed scheme, which consists basically of the addition of some state transitions and their output to the state transition graph (STG) of the machine. A test generation procedure is described which requires neither fault simulation nor manipulation of the machine's STG. - Author(s): M.J. Avedillo ; J.M. Quintana ; J.L. Huertas
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 4, p. 229 –237
- DOI: 10.1049/ip-cdt:19941228
- Type: Article
- + Show details - Hide details
-
p.
229
–237
(9)
The authors describe a state assignment algorithm for FSMs which produces an assignment of non-necessarily distinct, and eventually, incompletely specified codes. In this new approach, state-reduction and state assignment are dealt with concurrently, and a restricted state splitting technique is explored. The algorithm is particularly appropriate for machines with compatibility relations among its states because the potentials of state merging are exploited during the state assignment step. The input to SMAS, the program implementing the algorithm, is a symbolic cover of the FSM. The output is a Boolean representation of both next state and output functions suitable to minimise with ESPRESSO. The machines in the MCNC benchmark set are used to test the new algorithm and to compare it with a well known state assignment program. - Author(s): S.Y. Yuan
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 4, p. 238 –242
- DOI: 10.1049/ip-cdt:19941165
- Type: Article
- + Show details - Hide details
-
p.
238
–242
(5)
Decentralised protocols can be characterised by successive rounds of message interchanges. We show that at least kN((N1/k)-1) messages are required for fully decentralised evaluating functions that are both associative and commutative if k rounds of message interchanges are used in an N-node system. We then present a family of fully decentralised algorithms that requires, at most, a total of kN((N1/k)-1) messages to be sent with k rounds of message interchanges. Therefore, the family of algorithms is optimal with respect to the total number of messages exchanged among the processing nodes. The problems which can be modelled as an evaluation of associative and commutative functions include extrema findings and distributed transaction commitments. - Author(s): G. Masera ; G. Piccinini ; M. Zamboni
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 4, p. 243 –248
- DOI: 10.1049/ip-cdt:19941290
- Type: Article
- + Show details - Hide details
-
p.
243
–248
(6)
The high level of complexity and the high degree of parallelism involved in several modern microprogrammed systems imply the design of control units having an extremely large microcode. Consequently, the necessity of limiting the size of the control store pushed research in two directions: microcode compaction, for reducing the number of words, and microcode bit minimisation, for reducing the number of control bits in a single word. In this paper, a new method for the optimisation of microword length in large microprogrammed systems is addressed. Microcode bit optimisation is formulated as a covering problem applied to a choice of maximal compatibility classes, collecting operations that can share the same bit held in the microcode. Comparisons with most of the published approaches are given using some benchmarks: results obtained show that the proposed method saves microcode bits in several cases, while in the largest examples it grants a significant reduction in computation time. - Author(s): J. He and T. Kiesler
- Source: IEE Proceedings - Computers and Digital Techniques, Volume 141, Issue 4, p. 249 –252
- DOI: 10.1049/ip-cdt:19941272
- Type: Article
- + Show details - Hide details
-
p.
249
–252
(4)
The paper proposes the use of more than one hard problem in the design of cryptographic protocols to enhance their security. Specifically, both the discrete logarithm problem and the factorisation problem are embedded in the process of signing to enhance the security of the original El Gamal signature scheme.
Quick recovery of two embedded complete binary trees in a hypercube
Pipeline ring data-flow architecture for solving large iterative structures
FSMTEST: synthesis for testability and test generation of PLA-based FSM
State merging and state splitting via state assignment: a new FSM synthesis algorithm
Message optimal fully decentralised evaluation of associative and commutative functions
Minimisation of control store width in digital systems
Enhancing the security of El Gamal's signature scheme
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.