Algebraic approach to time borrowing

David Broomhead, Steve Furber, Marianne Johnson

Research output: Contribution to journalArticlepeer-review


This study describes a novel application of max-plus linear algebra to the timing of digital hardware. The authors give a rigorous, algorithmic approach to 'time borrowing' - a technique whereby the use of a multi-phase clock can allow for a more flexible, efficient use of time. In this approach the system is clocked periodically, but within each clock cycle processes interact asynchronously, allowing longer processes to be juxtaposed with shorter processes. The authors have shown that this problem can be solved completely using linear algebra defined over the max-plus semi-ring. This work establishes the mathematical foundation of an earlier, heuristic approach to the problem. ©The Institution of Engineering and Technology 2013.
Original languageEnglish
Pages (from-to)1-10
Number of pages9
JournalIET Computers and Digital Techniques
Issue number1
Publication statusPublished - 2013


  • max-plus semiring; max-plus linear algebra; algebraic approach; multiphase clock; digital hardware timing; time borrowing approach


Dive into the research topics of 'Algebraic approach to time borrowing'. Together they form a unique fingerprint.

Cite this