US5854918A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for self-timed algorithmic execution
Assignee: Ricoh Co Ltd
•
Filing: 1996-01-24
•
Granted: 1998-12-29
•
Expires: 2016-01-24
Abstract
Abstract An apparatus for self-timed algorithmic execution comprises a functional logic set, a reference clock input and a pulse sequencer. The functional logic set receives input data in synchrony with a reference pulse set received at the reference clock input; performs algorithmic computations on the input data at a maximal-rate set by the pulse sequencer in accordance with the physical characteristics of the functional logic; generates output data; and transmits the output data in synchrony with the reference pulse set. The maximal-rate set by the pulse sequencer is independent of the reference pulse set. A method for self-timed algorithmic execution comprises the steps of: transferring input data to a functional logic set in synchrony with a reference clock; generating a maximal-rate pulse sequence, for driving the functional logic set at a rate dependent upon an algorithm execution time for the functional logic set but independent of the reference clock; generating output data from the functional logic set in response to the maximal-rate pulse sequence; and transferring the output data from the functional logic in synchrony with the reference clock.
Inventors
- 👤 Michael A. Baxter
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:36
CPC Classifications
G; G06; G06F; G06F7/00
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
113 words
An apparatus for self-timed algorithmic execution in a globally synchronous, locally asynchronous system, the apparatus comprising: a functional logic set coupled to receive input data at a first rate, for generating output data at a second rate independent of the first rate, and coupled to transmit the output data at the first rate; and a self-timed pulse sequencer, for generating a self-timed pulse sequence corresponding to the second rate, the pulse sequencer coupled to control the functional logic; wherein: the functional logic set and the self-timed pulse sequencer operate in a globally synchronous, locally asynchronous manner; and the timing of the pulse sequence is independent of the timing of the functional logic set.
Claim 2
Independent Claim
113 words
An apparatus for self-timed algorithmic execution in a globally synchronous, locally asynchronous system, the apparatus comprising: a functional logic set coupled to receive input data at a first rate, for generating output data at a second rate independent of the first rate, and coupled to transmit the output data at the first rate; and a self-timed pulse sequencer, for generating a self-timed pulse sequence corresponding to the second rate, the pulse sequencer coupled to control the functional logic; wherein: the functional logic set and the self-timed pulse sequencer operate in a globally synchronous, locally asynchronous manner; and the timing of the pulse sequence is independent of the timing of the functional logic set.
Claim 3
Dependent Claim
29 words
The apparatus of claim 1, wherein: the functional logic set has a predicted execution time; and the second rate is a maximal rate based upon the predicted execution time.
Claim 4
Dependent Claim
45 words
The apparatus of claim 1, wherein the functional logic is located sufficiently proximate to the self-timed pulse sequencer within a set of hardware resources as to respond in substantially identical manner as does the self-timed pulse sequencer to operating parameter variations of the hardware resources.
Claim 5
Dependent Claim
18 words
The apparatus of claim 1, wherein the pulse sequencer comprises a delay unit that generates a self-timed oscillation.
Claim 6
Dependent Claim
25 words
The apparatus of claim 4, wherein the delay unit comprises a set of serially coupled logic devices, each logic device having a predictable propagation delay.
Claim 7
Dependent Claim
20 words
The apparatus of claim 5, wherein the set of serially coupled logic devices comprises a set of carry logic elements.
Claim 8
Dependent Claim
20 words
The apparatus of claim 6, wherein the set of carry logic elements comprises carry-propagate logic within a reconfigurable logic device.
Claim 9
Dependent Claim
51 words
The apparatus of claim 4, wherein the pulse sequencer further comprises sequence gate logic for generating a set of clocking signals, the sequence gate logic coupled to receive a delay unit output signal and coupled to deliver the set of clocking signals to the functional logic to provide the second rate.
Claim 10
Dependent Claim
31 words
The apparatus of claim 8, wherein the pulse sequencer further comprises a pulse counter for generating a pulse count signal, the pulse counter coupled to receive the delay unit output signal.
Claim 11
Dependent Claim
26 words
The apparatus of claim 9, wherein the pulse sequencer further comprises start logic for generating a start pulse to initiate the operation of the delay unit.
Claim 12
Dependent Claim
99 words
The apparatus of claim 4, wherein the functional logic comprises a multiplier, the multiplier comprising: a multiplexor coupled to receive a multiplicand; a partial product generator coupled to receive a multiplier and a subset of bits within the multiplicand, for generating a set of partial products; a partial product summer coupled to receive the set of partial products, for generating a partial product sum; and a product accumulator coupled to receive the partial product sum, for accumulating partial product sums to generate a product, wherein the multiplier is controlled according to the self-timed oscillation generated by the delay unit.
Claim 13
Dependent Claim
31 words
A pulse sequencer for operation in parallel with functional logic within a reconfigurable logic device, the pulse sequencer comprising a set of carry logic elements coupled to generate a self-timed oscillation.
Claim 14
Dependent Claim
31 words
A pulse sequencer for operation in parallel with functional logic within a reconfigurable logic device, the pulse sequencer comprising a set of carry logic elements coupled to generate a self-timed oscillation.
Claim 15
Independent Claim
167 words
An apparatus for controlling a self-timed algorithmic execution system, the self-timed algorithmic execution system comprising functional logic that receives input data and generates output data in globally synchronous, locally asynchronous operation in response to a set of control signals, the apparatus comprising: start logic coupled to receive a start signal and in response generate a start pulse; a delay unit coupled to receive the start pulse and in response generate a delay unit output signal and a feedback signal; a pulse counter coupled to receive the delay unit output signal and in response generate a pulse count signal and selectively generate a halt signal; and sequence gate logic coupled to receive the pulse count signal and in response generate the set of control signals; wherein: the start logic is coupled to receive the feedback signal and in response regenerate the start pulse if the halt signal has not been generated; and the timing of the pulse count signal is independent of the timing of the functional logic.
Claim 16
Independent Claim
167 words
An apparatus for controlling a self-timed algorithmic execution system, the self-timed algorithmic execution system comprising functional logic that receives input data and generates output data in globally synchronous, locally asynchronous operation in response to a set of control signals, the apparatus comprising: start logic coupled to receive a start signal and in response generate a start pulse; a delay unit coupled to receive the start pulse and in response generate a delay unit output signal and a feedback signal; a pulse counter coupled to receive the delay unit output signal and in response generate a pulse count signal and selectively generate a halt signal; and sequence gate logic coupled to receive the pulse count signal and in response generate the set of control signals; wherein: the start logic is coupled to receive the feedback signal and in response regenerate the start pulse if the halt signal has not been generated; and the timing of the pulse count signal is independent of the timing of the functional logic.
Claim 17
Independent Claim
112 words
A method for self-timed algorithmic execution in a globally synchronous, locally asynchronous system, for an apparatus comprising a functional logic set and a self-timed pulse sequencer, the method comprising the steps of: receiving input data at a first rate; generating a self-timed pulse sequence at a second rate independent of the first rate; processing the input data at the second rate in response to the self-timed pulse sequence; and outputting the output data at the first rate; wherein: the functional logic set and the self-timed pulse sequencer operate in a globally synchronous, locally asynchronous manner; and the timing of the pulse sequence is independent of the timing of the functional logic set.
Claim 18
Independent Claim
112 words
A method for self-timed algorithmic execution in a globally synchronous, locally asynchronous system, for an apparatus comprising a functional logic set and a self-timed pulse sequencer, the method comprising the steps of: receiving input data at a first rate; generating a self-timed pulse sequence at a second rate independent of the first rate; processing the input data at the second rate in response to the self-timed pulse sequence; and outputting the output data at the first rate; wherein: the functional logic set and the self-timed pulse sequencer operate in a globally synchronous, locally asynchronous manner; and the timing of the pulse sequence is independent of the timing of the functional logic set.
Claim 19
Dependent Claim
31 words
The method of claim 14, wherein the step of generating the pulse sequence is performed at a maximal rate dependent upon an execution time associated with the set of functional logic.
Claim 20
Dependent Claim
48 words
The method of claim 14, wherein: the step of receiving input data is performed in synchrony with a reference clock; the step of generating is performed at a self-timed rate independent of the reference clock; and the step of outputting is performed in synchrony with the reference clock.
Claim 21
Dependent Claim
35 words
The method of claim 16, wherein the step of generating comprises the steps of: generating a self-timed oscillation in response to a start signal; and maintaining the self-timed oscillation until a halt signal is received.
Claim 22
Dependent Claim
46 words
The method of claim 17, wherein the step of generating further comprises the steps of: generating a pulse count signal; and generating a set of control signals to control the processing of the input data at a rate corresponding to the period of the self-timed oscillation.
Claim 23
Dependent Claim
70 words
The method of claim 14, wherein the step of processing comprises the substeps of: generating a set of partial products by multiplying a multiplier and a subset of bits within a multiplicand; generating a partial product sum by adding the set of partial products; accumulating the partial product sum with a previous partial product sum; and repeating each substep within the step of processing until a multiplication product is generated.
Claim 24
Independent Claim
126 words
An apparatus for self-timed algorithmic execution in a globally synchronous, locally asynchronous system, the apparatus comprising: means for receiving input data at a first rate; means for generating a self-timed pulse sequence at a second rate, the second rate independent of the first rate; means for processing the input data at the second rate to generate output data in response to the self-timed pulse sequence; and means for outputting the output data at the first rate; wherein: the means for generating a self-timed pulse sequence, the means for receiving input data, and the means for processing the input data, operate in a globally synchronous, locally asynchronous manner; and the timing of the pulse sequence is independent of the timing of the means for receiving input data.
Claim 25
Independent Claim
126 words
An apparatus for self-timed algorithmic execution in a globally synchronous, locally asynchronous system, the apparatus comprising: means for receiving input data at a first rate; means for generating a self-timed pulse sequence at a second rate, the second rate independent of the first rate; means for processing the input data at the second rate to generate output data in response to the self-timed pulse sequence; and means for outputting the output data at the first rate; wherein: the means for generating a self-timed pulse sequence, the means for receiving input data, and the means for processing the input data, operate in a globally synchronous, locally asynchronous manner; and the timing of the pulse sequence is independent of the timing of the means for receiving input data.
Claim 26
Dependent Claim
17 words
The apparatus of claim 20, wherein the means for generating comprises means for generating a self-timed oscillation.
References Cited (Backward Citations)
US3222536A
Cited
US3358128A
Cited
US3553446A
Cited
US4322643A
Cited
US4682303A
Cited
US5117386A
Cited
US4707800A
Cited
US4737926A
Cited
US4876660A
Cited
US4841468A
Cited
US5047975A
Cited
US4972362A
Cited
US4982352A
Cited
US5153848A
Cited
US5173617A
Cited
US5511173A
Cited
US5018093A
Cited
US5038117A
Cited
US5175453A
Cited
US5109394A
Cited
US5483478A
Cited
US5566079A
Cited
US5511181A
Cited
US5450607A
Cited
US5553276A
Cited
US5509040A
Cited
US5710910A
Cited
US5576982A
Cited
US5502403A
Cited
US5566123A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-12-28 | 2002-06-29 | 2002-12-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-12-28 | 2006-06-29 | 2006-12-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-12-28 | 2010-06-29 | 2010-12-29 | $7700.00 | Window Closed / Lapsed |