More Web Proxy on the site http://driver.im/

Article

Free access

Proof of the equivalent realizability of a time-bounded arbiter and a runt-free inertial delay

Author:

B. I. StromAuthors Info & Claims

ISCA '79: Proceedings of the 6th annual symposium on Computer architecture

Pages 178 - 181

https://doi.org/10.1145/800090.802907

Published: 23 April 1979 Publication History

Abstract

This paper proves that, given a reliable time-bounded arbiter, it is possible to realize a reliable (i.e. runt-free) inertial delay, and vice-versa. It therefore shows that the time-bounded arbiter and the inertial delay are equally realizable. Consequently all theoretical limitations which apply to one will apply, in some form, to the other as well.

References

[1]

Cane, D.A., Dutton, D. R. and Gunther, J.M., "Synchronizer Circuit," U.S. Patent 3,997,872, Dec. 14, 1976.

[2]

Catt, I., "Time Loss Through Gating of Asynchronous Logic Signal Pulses," IEEE Transactions on Electronic Computers (Short Notes), EC-15, No. 1, pp. 108-111, Feb. 1966.

[3]

Chaney, T. J., "A Guide to More Reliable Synchronizer Designs," Technical Memorandum 207A, Computer Systems Laboratory, Washington University, St. Louis, Missouri, May 1974.

[4]

Chaney, T. J., "Macromodular Computer Design - Part 1 Development of Macromodules - Volume IV - The Synchronizer 'Glitch' Problem," Computer Systems Laboratory, Washington University, St. Louis, Missouri, Feb.1974. Avail: NTIS AD-783 874/1.

[5]

Chaney, T. J. and Molnar, C. E., "Anomalous Behavior of Synchronizer and Arbiter Circuits," IEEE Transactions on Computers, (Correspondence), C-22, No. 4, pp. 421-422,April 1973.

[6]

Chaney, T.J., Ornstein, S.M., and Littlefield, W. M., "Beware the Synchronizer," Digest of Papers of the 6th Annual IEEE Computer Society International Conference, pp.317-319, Sept. 1972.

[7]

Corsini, P., "n-User Asynchronous Arbiter," Electronics Letters,11, No. 1, pp. 1-2, Jan. 1975.

[8]

Couranz, G. R., "An Analysis of Binary Circuits under Marginal Triggering Conditions," Technical Report 15, Computer Systems Laboratory, Washington University, St.Louis, Missouri, Nov. 1969.

[9]

Couranz, G. R. and Wann, D. F., "Theoretical and Experimental Behavior of Synchronizers Operating in the Metastable Region," IEEE Transactions on Computers,C-24, No.6, pp. 604-616, June 1975.

Digital Library

[10]

Elineau, G. and Wiesbeck, W., "A New J-K Flip-Flop for Synchronizers," IEEE Transactions on Computers,C-26, No.12, pp. 1277-1278, Dec. 1977.

Digital Library

[11]

Friedman, A. D., "Feedback in Asynchronous Sequential Circuits," IEEE Transactions on Electronic Computers,EC-15,No. 10, pp. 740-749, Oct. 1966.

[12]

Huffman, D. A., "The Synthesis of Sequential Switching Circuits," J. Franklin Inst.,257, pp. 161-190, Mar. 1954.

[13]

Hurtado, M. M.; "Structure and Performance of Asymptotically Bistable Dynamical Systems," Sc.D. dissertation, Washington University, St. Louis, Missouri, 1975. Avail: Univ. Microfilms, Ann Arbor, Mich., Order No. 75-28041.

[14]

Kinniment, D. J. and Edwards, D. B. G., "Circuit Technology in a Large Computer System," The Radio and Electronic Engineer,43, No. 7, pp. 435-441, July 1973.

[15]

Kinniment, D. J. and Woods, J. V., "Synchronisation and Arbitration Circuits in Digital Systems," Proceedings of the Institution of Electrical Engineers (GB),123, No. 10, pp. 961-966, Oct. 1976.

[16]

Liu, B. and Gallagher, N. C., "On the 'Metastable Region of Flip-Flop Circuits," Proceedings of the IEEE (Letters),65, No. 4, pp. 581-583, April 1977.

[17]

Marino, L. R., "The Effect of Asynchronous Inputs on Sequential Network Reliability," IEEE Transactions on Computers, C-26, No. 11, pp. 1082-1090, Nov. 1977.

[18]

Mayne, D., "Minimize Computer 'Crashes'," Electronic Design, 22, No. 9, pp. 168-172, April 1974.

[19]

Mikami, Y., "Glitchless TTL Arbiter Selects First of Two Inputs," Electronics,50, No. 12, p. 136, June, 1977.

[20]

Patil, S. S., "Arbiters and Synchronizers," Project MAC Progress Report X, Massachusetts Institute of Technology, Cambridge, Massachusetts, pp. 24-28, July 1972-July 1973.

[21]

Patil, S. S., "Bounded and Unbounded Delay Synchronizers and Arbiters," Project MAC, CSG Memo 103, M.I.T., Cambridge, Mass., Aug. 1974. Avail: NTIS PB-237 046.

[22]

P&ecaron;chou&ccaron;ek, M., "Anomalous Response Times of Input Synchronizers," IEEE Transactions on Computers,C-25, No. 2, pp. 133-139, Feb. 1976.

[23]

Servít, M., "Hazard Correction in Asynchronous Sequential Circuits using Inertial Delay Elements," IEEE Transactions on Computers (Correspondence),C-22, No. 11, pp. 1041-1042, Nov. 1973.

[24]

Unger, S. H., Asynchronous Switching Circuits, New York, Wiley-Interscience, 1969.

Digital Library

[25]

Unger, S. H., "Asynchronous Sequential Switching Circuits with Unrestricted Input Changes," IEEE Transactions on Computers,C-20, No. 12, pp. 1437-1444, Dec.1971.

[26]

Unger, S. H., "Self-Synchronizing Circuits and Nonfundamental Mode Operation," IEEE Transactions on Computers (Correspondence),C-26, No. 3, pp. 278-281, March 1977.

[27]

Vosbury, M. K. and Arden, D. N., "Hazards in Asynchronous Sequential Circuits due to Unrestricted Input Changes," available from D. N. Arden, State University of New York, 1400 Washington Ave., Albany, N.Y. 12222.

[28]

Wormald, E.G., "A Note on Synchronizer or Interlock Maloperation," IEEE Transactions on Computers (Correspondence),C-26, No. 3, pp. 317-318, March 1977.

Cited By

Mendler MStroup T(1993)Newtonian arbiters cannot be proven correctFormal Methods in System Design10.1007/BF013840753:3(233-257)Online publication date: 1-Dec-1993
https://dl.acm.org/doi/10.1007/BF01384075
Barros JJohnson B(1983)Equivalence of the Arbiter, the Synchronizer, the Latch, and the Inertial DelayIEEE Transactions on Computers10.1109/TC.1983.167629232:7(603-614)Online publication date: 1-Jul-1983
https://dl.acm.org/doi/10.1109/TC.1983.1676292
Marino L(1981)General theory of metastable operationIEEE Transactions on Computers10.5555/1963635.196363830:2(107-115)Online publication date: 1-Feb-1981
https://dl.acm.org/doi/10.5555/1963635.1963638

Index Terms

Proof of the equivalent realizability of a time-bounded arbiter and a runt-free inertial delay

Recommendations

Ping-lock round robin arbiter

Arbiter is the core element in shared-resources systems such as in network-on-chip (NoC), conventional interconnection buses and computer network switch schedulers. Arbiters are located in the critical path delay (CPD) of these systems, that ...
Real-Time Implementation of GPS Aided Low-Cost Strapdown Inertial Navigation System

This work details the study, development, and experimental implementation of GPS aided strapdown inertial navigation system (INS) using commercial off-the-shelf low-cost inertial measurement unit (IMU). The data provided by the inertial navigation ...
Proof-Guided Underapproximation Widening for Bounded Model Checking
Computer Aided Verification
Abstract
Bounded Model Checking (BMC) is a popularly used strategy for program verification and it has been explored extensively over the past decade. Despite such a long history, BMC still faces scalability challenges as programs continue to grow larger ... $^{}$ $^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '79: Proceedings of the 6th annual symposium on Computer architecture

April 1979

246 pages

ISBN:9781450373975

DOI:10.1145/800090

Copyright © 1979 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

ACM: Association for Computing Machinery
IEEE: Institute of Electrical and Electronics Engineers

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 April 1979

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
338
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)7

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mendler MStroup T(1993)Newtonian arbiters cannot be proven correctFormal Methods in System Design10.1007/BF013840753:3(233-257)Online publication date: 1-Dec-1993
https://dl.acm.org/doi/10.1007/BF01384075
Barros JJohnson B(1983)Equivalence of the Arbiter, the Synchronizer, the Latch, and the Inertial DelayIEEE Transactions on Computers10.1109/TC.1983.167629232:7(603-614)Online publication date: 1-Jul-1983
https://dl.acm.org/doi/10.1109/TC.1983.1676292
Marino L(1981)General theory of metastable operationIEEE Transactions on Computers10.5555/1963635.196363830:2(107-115)Online publication date: 1-Feb-1981
https://dl.acm.org/doi/10.5555/1963635.1963638

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten