Pipeline array

A pipeline array includes a register, a pipeline clock input, and Narrow Pulse Triggered Latches (NPTL) stages connected in series. Each NPTL stage includes a Latch Pulse Generator (LPG) and a parallel set of single latches clocked by the LPG. The latches provide the parallel data input and the parallel data output of the stage. Each LPG provides a narrow latch clock pulse in response to a Pipeline Clock Pulse (PCP) supplied to the register and the last stage of latches. Each PCP arrives at each preceding LPG in the array after a delay provided by intervening time delay units. The delays increase for each preceding stage with the least delay at the penultimate stage and with the greatest delay at the first stage. The data input of the first stage is connected to the output of the register. The data input of the each of other stage is connected to the data output of the preceding stage in the array.

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates to buffer storage systems and more particularly to pipelined buffer storage systems and methods of operation thereof.

2. Description of Related Art

In many networked applications, it is necessary to buffer large amounts of data in a pipeline buffer. A pipelined buffer includes “N” hardware stages, where N is a positive integer, broken down into a series of memory registers connected in series for storing a sequence (line) of data bits temporarily passed from one register to the next, as in a bucket brigade. That is to say that data bits are moved in series from one memory register to the next register in the pipeline, one by one, with each register being replenished by the next data bit in line. Since the “N” stages operate substantially concurrently, a pipeline can operate faster than a non-pipelined system. A pipeline buffer is a First-In-First-Out (FIFO) buffer in which one “word” of data is written into the buffer and one “word” of data is read from the buffer on each clock cycle. The number of “words” stored in the buffer is a fixed value equal to the depth of the pipeline. For example, if the depth of the pipeline is N, the word written into the buffer at cycle “i” is read from the buffer substantially later at cycle “i+N”. The word read from the buffer at cycle “i” was written into the buffer at cycle “i−N”.

Referring toFIG. 1, a schematic circuit diagram is shown of a common, prior art pipeline buffer7, which includes a set of N multi-bit registers REG110, REG211, REG312, . . . REGN−113, and REGN14, where N is a positive integer equal to the number of registers therein. Input data DATAIN[i] is submitted to the pipeline buffer7on input bus lines8. The pipeline buffer7is configured as sets of multi-bit shift registers, where data is shifted from one of the sets of multi-bit registers10-14to the next set of multi-bit registers on each clock cycle, as shown in FIG.1.

Each bit of each of the multi-bit registers10-14ofFIG. 1is typically implemented as a flip-flop. Since two latches are required to form each flip-flop, that means that a substantial area is required for each flip-flop. The same clock signal CL1on line9clocks all of the multi-bit registers10-14in the pipeline buffer7. Output data (DATAOUT[i]) is delivered from the last multi-bit register14on bus lines15simultaneously. It is noted that the data out from pipeline buffer7on bus lines15is defined by the relationship DATAOUT[i]=DATAIN[i−N].

There are two problems with the typical implementation of the type of pipeline buffer array7shown inFIG. 1, which are as follows:

1. Clock Skew Problems

First, in an Application Specific Integrated Circuit (ASIC) design environment, where flip-flop cells (e.g. registers10-14) are automatically placed and routed, it is difficult to manage clock skew to avoid fast path (early mode) failures without adding a significant amount of delay into each register-to-register path.

2. Delays Caused by Excessive Chip Area Requirements

Secondly, added delays typically contribute to the second problem, which is that the chip area required by such a pipeline buffer array7can become quite large.

FIG. 2shows a schematic circuit diagram of alternative prior art FIFO (First In First Out) buffer configuration17which utilizes a two-port memory array23, consisting of a write port24for writing data to a selected write address and a read port25for reading data from a selected read address. A FIFO buffer typically also includes address counters and address comparison logic to detect when there is data in the FIFO buffer (read and write addresses are not equal) vs. when the FIFO buffer is “empty” (read and write addresses are equal).

An clock pulse19is applied to a register20which supplies an output on line21to node21′, which goes to incrementer22which adds a plus one (+1) to the register20. The value on node21′ from register20passes through line21to the write address input to the memory array23and via the −N subtractor25through line25′ to the read address input to memory array23. The input data (DATAIN[i]) is submitted on bus lines18to the data input of memory array23and data out (DATAOUT[i]) from the two-port memory array23is delivered to output bus lines23′ from the two-port memory array23.

FIG. 2shows a FIFO buffer that can easily be tailored to implement a pipeline buffer array23. In the case ofFIG. 2, a problem that needs to be solved is illustrated which is that the read and write addresses are always at a fixed difference, N, from each other (modulo M, where M is the number of words in the array).

The memory array implementation ofFIG. 2would solve the first problem, i.e. the clock skew problem, because of its regular, predetermined and pre-characterized layout. However, because of the overhead of address decoding logic and testability, the memory array implementation is larger than the flip-flop implementation unless the number of stages, N, in the pipeline is large (≧16), which is a problem in that excessive area on the chip is required.

Because typical applications require fewer than a dozen pipeline stages, an alternative implementation is required.

SUMMARY OF THE INVENTION

The advantage(s) of using the present invention are the combination of the benefits of the memory array (regular, predetermined, precharacterized layout) with the area advantages afforded by single latch storage elements instead of double latch flip-flops.

In accordance with this invention, a system is provided comprising a pipeline clock generator for generating a series of wide (relatively long duration) Pipeline Clock Pulses (PCP)s and a pipeline clock line for receiving the series of wide PCPs. A register is provided having a register clock input, a register data input and a register data output. There are N Narrow Pulse Triggered Latch (NPTL) stages including N Latch Pulse Generators (LPG)s and N parallel sets of latches, with a parallel set of single latches for each stage, where N is a positive integer, including at least a first NPTL stage, a penultimate NPTL stage, and a last NPTL stage.

Each NPTL stage includes a latch and an LPG. The LPG is adapted to generate a latch clock pulse and includes a pipeline clock pulse input and an LPG pulse output. The latch includes a latch data input, a latch data output, and a clock input connected to the LPG pulse output of the LPG. The LPG pulse output is connected to trigger the latch when the LPG is activated by activation of the pipeline pulse input. Each latch data output is connected in series to a latch data input of a successive NPTL stage except that the latch data output of the last NPTL stage is connected as a pipeline data output. The latch data input of the first NPTL stage is connected to the register data output. The pipeline clock line is connected to the register clock input and the pipeline clock pulse input of the LPG of the last NPTL stage. There are N-1time delay units. Each of the time delay units is connected to the pulse input of an LPG except for the last NPTL stage. Thus, the time delay units activate the LPGs in a bucket brigade fashion.

Preferably, the N−1 time delay units are connected in series with nodes connected therebetween. Each of the N−1 time delay units has a delay input and a delay output. There are a first time delay unit and a last time delay unit. The delay input of the first time delay unit is connected to the pipeline clock line. The delay output of the first time delay unit is connected to the LPG of the penultimate NPTL stage. The delay output of the last time delay unit is connected to the LPG of the first NPTL stage. Preferably, the delay output of one of the N−1 time delay units is connected to the pipeline clock pulse input of the LPG of each NPTL stage from the penultimate NPTL stage to the first NPTL stage.

Preferably, the N−1 time delay units have N−1 time delay unit inputs and N−1 time delay unit outputs, which are connected in series. The pipeline clock pulse input of each of the LPGs is connected to one of the N−1 time delay unit outputs aside from the last NPTL stage.

Preferably, the LPG of each NPTL stage includes a dual input AND circuit, which has a first input connected directly to the clock input of the latch of that NPTL stage. In addition, the AND circuit has a second input connected from the pipeline clock pulse input of that NPTL stage through a LPG delay circuit and an inverter.

In accordance with another aspect of the invention, a pipeline array includes a pipeline data input, a pipeline data output, and a pipeline clock line. A pipeline clock pulse generator for generating a series of wide Pipeline Clock Pulses (PCP)s connected to the pipeline clock line. An input register has a register data input connected to the pipeline data input. The input register also has a register data output and a register clock input connected to the pipeline clock line. There are N NPTL stages including N parallel sets of single latches with one parallel set of single latches for each stage, N Latch Pulse Generators (LPG)s and N−1 time delay units, where N is a positive integer. Each of the NPTL stages comprising a single latch having with a latch data input, a latch data output and a latch clock input and a LPG. Each LPG has an LPG input and an LPG output. The LPG output is connected to the latch clock input of that NPTL. Each LPG is adapted to provide a narrow trigger pulse in response to a PCP. The N NPTL stages include a first NPTL stage and a last NPTL stage. The register data output is connected to the latch data input of the first NPTL stage. The N latch stages are connected in series. The latch data output of each previous NPTL stage is connected to the latch data input of a successive NPTL stage except for the last NPTL stage which is connected to the pipeline data output. N−1 time delay units are connected in series to provide delayed clock signals to the LPGs except for the last NPTL stage. The LPG input of the last NPTL stage is connected to the pipeline clock line. Thus, the time delay units activate the LPGs to transfer data from a preceding NPTL stage to a successive NPTL stage in a bucket brigade fashion starting with the last NPTL stage and ending with the first NPTL stage during a single pipeline clock pulse.

DESCRIPTION OF THE PREFERRED EMBODIMENT

FIG. 3Ais a schematic circuit diagram of a system26, in accordance with this invention including a Pipeline Clock Pulse (PCP) generator29G and a pipeline buffer array27which receives Pipeline Clock Pulses (PCP)s from the PCP generator29G. The pipeline buffer array27is formed by a register50, and a set of cascade connected of N Narrow Pulse Triggered Latch (NPTL) stages81,82,83, . . . ,87,88, and time delay units33,34, . . . ,37,38,39(where N is a positive integer). The pipeline buffer array27receives an input comprising multi-bit DATAIN[i] on bus lines28. In addition, the pipeline buffer array27is clocked by the PCPs on a pipeline clock line29comprising a series of relatively wide PCPs (relatively long duration PCPs) from the PCP generator29G. The DATAIN[i] bus lines28are connected to the data (D) input of the FF register50. The FF register50preferably comprises a conventional multi-bit unit. An edge-triggered input is formed by a set of multiple edge triggered type-D flip-flop circuits. There is one type D flip-flop circuit for each of the multiple bits shown inFIG. 6including latch50′ and latch50″ and an inverter70, described in more detail below. Preferably, the type-D flip-flops are of the type described by John F. Wakerly “Digital Design Principles and Practices” Prentice Hall, page 540.

The FF register50, which is the first stage of the pipeline27, is followed by the NPTL1-NPTLNseries stages81,82,83, . . . ,87,88connected in series with multiple bits in each of those N stages. Data flows from one NPTL stage to the next NPTL stage peristaltically, i.e. in a bucket brigade manner, in response to a series of delayed PCPs propagated in the reverse direction from the pipeline clock line29through the time delay units33,34, . . . ,37,38,39to trigger each of the NPTLN-NPTL1series stages88,87, . . . ,83,82,81to receive data from the previous stage in that order, seriatim. Each PCP is supplied directly, without passing through a delay unit to the register50and to the last, NPTLNstage88. Each PCP arrives at each preceding NPTL stage in the array26after a delay provided by intervening time delay units33,34, . . . ,37,38,39. The delays increase for each preceding stage with the least delay at the penultimate stage87and with the greatest delay at the first stage81.

The PCP generator29G supplies the underlayed, wide PCPs to all of the segments of pipeline clock pulse line29. The PCPs pass through node29′ and segments of pipeline clock pulse line29to the clock input of the FF register50. The PCPs also pass through the segments of pipeline clock pulse line29, the node29′, and node29″ to the clock input of the last NPTLNstage88, as well as, the input of DN−1time delay unit33which feeds delayed PCPs to the remainder of the NPTL stages81,82,83, . . . ,87.

At time t, a PCP on line29causes the data input of register50to receive data on bus line28.FIG. 8shows the sequence of pulses and data transmission which starts at time “t”. Note that the generation and the timing of a series of latch pulses P1, P2, PN−2, PN−1, PNshown inFIG. 8is described below with respect toFIGS. 3B,4,5A and5B.

At the same time, that initial, undelayed PCP on line29causes the NPTLNstage88, which is the last stage in the array27, to receive whatever data is stored in the penultimate stage, NPTLN−1stage87as shown by a first latch pulse P1in FIG.8. Also at that time that initial, undelayed PCP on line29causes the DN−1time delay unit33to produce a delayed PCP on line73, delayed by time δ (at time t+δ) as shown for pulse P2in FIG.8.

At time t+δ, the delayed PCP on line73causes the penultimate NPTLNstage87in the array27to receive whatever data is stored in the previous NPTLN−2stage (not shown). The delayed PCP on line73causes the DN−2time delay unit34to produce a PCP delayed by time 2δ on line74delayed by an additional delay time “δ” (at time t+2δ). The stage connected to line74is not shown inFIG. 8for convenience of illustration.

At time t+(N−3)δ, a delayed PCP on line76causes a D3time delay unit37to produce a PCP on line77that has been delayed by an accumulated delay time (N−3)δ on line77(at time t+(N−3)δ). That causes the NPTL3stage83to receive whatever data is stored in the previous, NPTL2stage82at time t+(N−3)δ, as shown for pulse PN−2in FIG.8.

The delayed PCP on line77causes the D2time delay unit38to produce a PCP delayed by time (N−2)δ on line78delayed by an additional delay time “δ” at time t+(N−2)δ. That causes the NPTL2stage82to receive whatever data is stored in the previous NPTL1stage81(at time t+(N−2)δ), as shown for pulse PN−1in FIG.8.

The delayed PCP on line78causes the D1time delay unit39to produce a PCP delayed by time (N−1)δ on line79delayed by an additional delay time “δ” at time t+(N−1)δ. That causes the NPTL1stage82to receive whatever data is stored in the previous stage, i.e. FF register50(at time t+(N−1)δ) as shown for pulse PNin FIG.8.

FIG. 3Bshows the system26ofFIG. 3Ain more detail with the components of the series of NPTL1-NPTLNstages81,82,83, . . . ,87,88, which include a series of parallel sets of single latches including an L1parallel set of single latches51, an L2parallel set of single latches52, an L3parallel set of single latches53, an LN−1parallel set of single latches57and an LN−1parallel set of single latches58. A number of Latch Pulse Generators (LPG)s42,43, . . . ,47,48and49are also included to trigger the clock inputs of the parallel sets of latches58,57, . . . ,53,52,51in that order, as will be described below.

The first NPTL1stage81is formed by the LPG49, a line49′, and the L1parallel set of single latches51. The input of LPG49is connected to line79. The output of LPG49is connected by line49′ to the clock input of the L1parallel set of single latches51. When the L1parallel set of single latches51is triggered, it latches data supplied to its data input on bus line60. In response to the rise of a delayed PCP on line79, the LPG49generates a latch pulse PNwhich passes through line49′ to trigger the L1parallel set of single latches51to latch data supplied from FF register50on bus line60.

The second NPTL2stage82is formed by the LPG48, a line48′, and the L2parallel set of single latches52. The input of LPG48is connected to line78. The output of LPG48is connected by line48′to the clock input of the L2parallel set of single latches52. When the L2parallel set of single latches52is triggered, it latches data supplied to its data input on bus line61. In response to the rise of a delayed PCP on line78, the LPG48generates a latch pulse PNwhich passes through line48′ to trigger the L2parallel set of single latches52to latch data supplied from L1parallel set of single latches51on bus line61.

The third NPTL3stage83is formed by the LPG47, a line47′, and the L3parallel set of single latches53. The input of LPG47is connected to line77. The output of LPG47is connected by line47′ to the clock input of the L3parallel set of single latches53. When the L3parallel set of single latches53is triggered, it latches data supplied to its data input on bus line62. In response to the rise of a delayed PCP on line77, the LPG47generates a latch pulse PN−2which passes through line47′ to trigger the L3parallel set of single latches53to latch data supplied from L2parallel set of single latches52on bus line62.

Then a gap is shown in the array followed by the NPTLN−1stage87that is formed by the penultimate clock LPG43and the penultimate LN−1parallel set of single latches57.

The penultimate NPTLN−1stage87comprises the LPG43, a line43′, and the penultimate, LN−1parallel set of single latches57. The input of LPG43is connected to line73. The output of LPG43is connected by line43′ to the clock input of the LN−1parallel set of single latches57. When the LN−1parallel set of single latches57is triggered, it latches data supplied to its data input on bus line66from a previous parallel set of single latches (LN−2in a stage NPTLN−2not shown for convenience of illustration). In response to the rise of a delayed PCP on line73, the LPG43generates a latch pulse P2which passes through line43′ to trigger the LN−1parallel set of single latches57to latch data supplied from the previous (LN−2) parallel set of single latches on bus line66.

At the end of the array, the last NPTLNstage88comprises the LPG42, a line42′, and the penultimate, LNparallel set of single latches58. The input of LPG42is connected to pipeline clock line29. The output of LPG42is connected by line42′ to the clock input of the LNparallel set of single latches58. When the LNparallel set of single latches58is triggered, it latches data supplied to its data input on bus line67from the previous LN−1parallel set of single latches57. In response to the rise of an PCP on line29at time “t”, which has not been delayed, the LPG42generates a latch pulse P1which passes through line42′ to trigger the LNparallel set of single latches58to latch data supplied from the previous LN−1parallel set of single latches57on bus line67.

Next a description is provided of the timing of the series of the initial and delayed PCP latch pulses (between the beginning and the end of the duration of a given PCP), which latch pulses are applied to the various LPGs and latches. Initially, the last LNparallel set of single latches58receives a pulse P1on line42′ from the LPG42at time “t” in response to the PCP on line29. Then, LN−1parallel set of single latches57receives the pulse P2on line43′ from LPG43at time t+δ in response to the arrival of the rise of the delayed PCP, which has been delayed by the time δ. Some time later, L3parallel set of single latches53receives pulse PN−2on line47′ from LPG47at time t+(N−3)δ, after the arrival of the rise of the PCP has been delayed by the time +(N−3)δ. A short time later, the L2parallel set of single latches52receives pulse PN−1on line48′ from LPG48at time t+(N−2)δ. Finally, the L1parallel set of single latches51receives pulse PNon line49′ from LPG49at time t+(N−1)δ.

In summary, the register50, which is the first stage of the pipeline27, is followed by the N L1-LNparallel sets of single latches51,51,53, . . . ,57,58in N NPTL stages81,81,83,87,88connected in series with multiple bits in each of those N stages. Data flows from stage to stage of the L1-LNstages peristaltically, i.e. in a bucket brigade manner, in response to a series of delayed clock pulses propagated in the reverse direction from pipeline clock line29through the time delay units33,34, . . . ,37,38,39to trigger each of the LN-L1parallel sets of single latches58,57, . . . ,53,52,51in that reverse order to receive data from the previous stage in that order, seriatim.

The initial PCP is supplied on line29to the input of the LPG42which generates the latch pulse P1on line42′ thereby triggering the last, LN−1parallel set of single latches58, causing the LNparallel set of single latches58of NPTLNstage88to receive data from the previous stage LN−1parallel set of single latches57in NPTLN−1stage87.

A delayed PCP, which was delayed by time “δ” by DN−1time delay unit33, is supplied via node33′ on line73to the next to last (penultimate) stage NPTLN−1stage87in response to the PCP on line29. That delayed PCP causes the LPG43to provide a latch pulse P2on line43′ triggering the LN−1parallel set of single latches57of the NPTLN−1stage87to receive data from the previous stage, which is not shown for convenience of illustration.

After the delay time of “δ” provided by the first delay unit33, a delayed PCP from DN−1time delay unit33is supplied via node33′ to DN−2time delay unit34. An even further delayed PCP, with a delay time of “2δ” is supplied via node34′ on line74by DN−2time delay unit34on line74to the next previous stage that would be NPTLN−2, which is also not shown for convenience of illustration, which operates in like manner to the other stages, as will be well understood by those skilled in the art.

Now let us consider the input to line76which receives a substantially delayed PCP, which has been delayed by time (N−4)δ from the time t by N−4 delay units including delay units33and34. Line76supplies that substantially delayed PCP to D3time delay unit37which causing the LPG47to generate latch pulse PN−2, (after the delay time of (N−3)δ from time t) to trigger the L3parallel set of single latches53of NPTL3stage83to receive data from the previous stage L2parallel set of single latches52.

The delayed PCP from D3time delay unit37is supplied via node37′ to D2time delay unit38at time (N−3)δ. Then the D2time delay unit38generates a delayed PCP causing the LPG48to generate latch pulse PN−1(after the delay time of (N−2)δ from time t) to trigger the L2parallel set of single latches52of NPTL2stage82to receive data from the previous stage L1parallel set of single latches51.

The delayed PCP from D2time delay unit38is supplied via node38′ to D1time delay unit39which generates a delayed PCP,causing the LPG49to generate latch pulse PNafter a delay time of (N−1)δ to trigger the L2parallel set of single latches51of NPTL1stage81to receive data from the register50.

Reverse Sequence of Narrow Latch Clock Pulses

InFIG. 4, the pipeline buffer array27includes a N clocking LPGs42,43, . . . ,47,48,49in the array provided to trigger operation of the N stages of multiple bit, parallel sets of single latches58,57, . . . ,53,52,51. Each of the LPGs42,43, . . . ,47,48,49is activated to make a data transfer by a separate clock input supplied thereto at a successively later time by applying a narrow, latch clock pulse P1, P2, . . . PN−2, PN−1, PNto the respective one of the N stages of multiple bit, i/e. parallel, sets of single latches58,57, . . . ,53,52,51with which it is associated in a backward moving, i.e. reverse, sequence. That is to say that LNparallel set of single latches58is activated to transfer and receive data first, followed by LN−1parallel set of single latches57, . . . followed by L3parallel set of single latches53, followed by L2parallel set of single latches52, followed by L1parallel set of single latches51which is in the first NPTL1stage81of the array27.

Each cycle of narrow, latch clock pulses P1, P2, . . . PN−2, PN−1, PNfrom the clocking network starts when the leading edge of a wide, PCP is received by the stage N LPG42on pipeline clock line29. The narrow, latch clock pulse on the output line42′ from stage N LPG42is supplied to trigger the clock input of the multiple bit, parallel set of single latches58for the last stage N in the pipeline buffer array27.

The triggering of the LNparallel set of single latches58is followed later, after a short time delay interval provided by delay DN−1circuit33, by a narrow, latch clock pulse on line43′ to the multiple bit parallel set of single latches57of the next LN−1to the last NPTLN−1stage88in the pipeline buffer array27. Each LPG42,43, . . . ,47,48,49in succession, in that order, generates a narrow, latch clock pulse P1, P2, . . . PN−2, PN−1, PNrespectively to activate the corresponding one of the multiple bit, parallel sets of latches58,57, . . . ,53,52, until finally LPG49applies an identical narrow, latch clock pulse PNon line49′ to the latch clock input of the multiple bit, parallel set of single latches51for stage1after the sum of N−1 intervals of delay provided by all of the DN−1, . . . , D3, D2, D1time delay units33, . . . ,37,38,39respectively.

Once for each rising clock edge of a pipeline clock signal, at time “t”, on pipeline clock line29, a new set of data bits is captured by the FF register50. At approximately the same time “t”, a pipeline clock signal on line29triggers the initial LPG42to generate the narrow, latch clock pulse P1on line42′ to trigger the LNparallel set of single latches58causing the set of data in LN−1parallel set of single latches57to be latched (copied) into the LNparallel set of single latches58which are in the NthNPTL stage of latches in the pipeline buffer array27.

Then, at a later time, determined by the delay time of the first time delay unit DN−1, it provides an output on line73which triggers the LPG43to supply a narrow, latch clock pulse P2on line43′ to the clock input of LN−1parallel set of single latches57. As a result data from LN−2parallel set of single latches (not shown) is latched (copied) into LN−1parallel set of single latches57.

Similarly, after subsequent delay intervals provided by time delay units not shown, data in each of the Lilatches is copied into each corresponding one of the Li+1parallel set of single latches in response to a clocking pulse from the “i+1” stage LPG (not shown) to the in Liparallel set of single latches (not shown), etc. where “i” is a positive integer.

Subsequently, after its corresponding delay time, the time delay unit D3provides an output on line77after N−2 intervals of delay which triggers narrow LPG47to supply a narrow, latch clock pulse PN−2on line47′ to cause a set of data in L2parallel set of single latches52to be latched into L3parallel set of single latches53.

Then a short interval later after a delay determined by time delay unit D2, it provides an output on line78after N−1 intervals of delay which triggers narrow LPG48to supply a narrow, latch clock pulse PN−1on line48′ to cause a set of data in L2parallel set of single latches52to be latched (copied) into L2parallel set of single latches53, in response to a clocking pulse from the third LPG47to the LN−1parallel set of single latches57.

Finally after its corresponding delay time, time delay unit D1provides an output on line79after N intervals of delay which triggers LPG49to supply a narrow, latch clock pulse PNon line49′ to cause data in the input, FF register50to be latched (copied) into L1parallel set of single latches51. Then, the pipeline buffer array27is ready to accept the next “word” of data at the input bus lines28.

More specifically, for each rising clock edge on pipeline clock lines29that passes through to clock the FF register50(the flip-flop registers), starting at time t=0 new data on bus line28is captured into and that data is propagated therefrom on bus lines60to the proximal L1parallel set of single latches51in the pipeline array27. Subsequently, the L1parallel set of single latches51latches that data, but only when it is enabled by a latch clock pulse on latch clock pulse input line49′ to L1parallel set of single latches51. The latch clock pulse on latch clock pulse input line49′ to L1parallel set of single latches51will occur after the time delay provided by all of the DN−1, . . . , D3, D2, D1time delay units33,37,38,39, as explained in detail above.

Referring toFIGS. 3B,5A and8, at time t=0 the rising clock edge on the pipeline clock lines29also causes the distal LPG42to create a narrow, latch clock pulse P1on the latch clock pulse input line42′ to the distal LNparallel set of single latches58in the pipeline27, latching the data on the bus lines67from the LN−1parallel set of single latches57into the LNparallel set of single latches58. The new data in the LNlatch58is immediately propagated from the distal LNparallel set of single latches58to the distal output bus lines68of the pipeline buffer27.

After a time delay D determined by the time delay unit33, clock input73to the LPG43rises, causing the LPG43to create a narrow, latch clock pulse on the latch clock pulse input line43′ at time t=t+δ, latching the data on the lines66into the LN−1parallel set of single latches57. The new data in the LNparallel set of single latches57is propagated to the bus lines67. Similarly, the parallel set of single latches Liare successively updated with new data from the parallel set of single latches Li−1until finally the parallel set of single latches L151is updated with the data on the lines60from the FF register50at an approximate time t=t+(N−1)δ, where each stage provides a time delay of about “δ”.

FIG. 5Ais a schematic diagram of L1, L2, L3, . . . , LN−1, and LNtype-D parallel sets of latches51,52,53,57and58, which are substantially identical to each other of the kind employed in FIG.3. The type-D latches are of the type described by John F. Wakerly “Digital Design Principles and Practices” Prentice-Hall, Third Edition, (updated 2001) at pages 538-541, where it is stated at page 540 that “A positive-edge-triggered D flip-flop combines a pair of D latches . . . ”. When the latch clock line42′ is high at the time of the narrow, latch clock pulse P1, input data on bus line67is propagated to output bus line68. Later, when latch clock line43′ is high at the time of pulse P2, input data on bus line66is propagated to output bus line67. Substantially later, when the latch clock line47′ is high at the time of the pulse PN−2, input data on the bus line62is propagated to the output bus line63. Still later, when the latch clock line48′ is high at the time of the pulse PN−1, input data on the bus line61is propagated to the output bus line62.

Finally, when the latch clock line47′ is high at the time of pulse PN, input data on the bus line60is propagated to the output bus line61. Note that, for example when the latch clock line49′ is high at the time of pulse PNinput data on bus line61is propagated to the output bus line62. Finally, when the latch clock line47′ is high at the time of pulse PN, input data on bus line60is propagated to output bus line61.

Note that, for example when the latch clock line49′ is high in response to generation of the latch clock pulse PN, input data60is propagated by the L1parallel set of single latches51to output61. On the other hand, when latch clock line49′ is low, output61is held to its previous logic state. This circuit is known in the art as a transparent latch. The L2, L3, . . . , LN−1, and LNparallel sets of latches52,53,57and58operate in the same way.

FIG. 5Ais a representative logic diagram of the combination of an LPG42and a single latch representative of the parallel set of single latches58, of the NLTLNstage88, which are identical to the other LPGs43, . . . ,47,48, and49and parallel sets of latches57. . . ,53,53, and51shown inFIGS. 3B, and4.

The LPG42is adapted to generate a narrow, latch clock pulse in response to the leading edge of a clock signal consists of a time delay unit72, an inverter72′ and an AND gate72″. The AND gate72″ has one of its two inputs connected to the pipeline clock line29. The time delay unit72also receives its input on pipeline clock line29, and in turn supplies its output to inverter72′, which then supplies its output to the other input of and gate72″. While the input on the pipeline clock line29is low, output line42′ from the LPGs42is low. In response to a rising transition of the input on the pipeline clock line29, the output line42′ goes high for a short period of time determined by the time delay unit72and then the output line42′ returns low.

The LPGs4243, . . . ,47,48, and49are logic units known in the art as a Pulse Generators (PG)s and are referred to herein as an LPGs since they are connected to trigger the respective clock inputs of the parallel sets of latches58,57, . . . ,53,52,51. The short period of time of each of the narrow, latch clock pulses P1, P2, . . . PN−2, PN−1, PNis about an order of magnitude shorter than the wide PCPs on line29and the delayed PCPs on the lines,73,77,78, and79as seen on FIG.8.

FIG. 5Bshows the structure of the latch51which is a single latch representative of a set of parallel latches in NLTL1stage81and the clock LPG49of the NLTL1stage81which has identical components and operates in an analogous fashion to the circuits ofFIG. 5A, as do the other NPTL stages82,83, and87, which will be well understood by those skilled in the art.

In response to each PCP, all of the resultant, latch clock pulses P1, P2, . . . PN−2, PN−1, PN, that are narrow relative to the wide PCPs, are generated before the next PCP is generated on line29. Thus, the sequence of data transfers from the parallel set of single latches L1to parallel set of single latches LN, propagated by the bucket brigade function, is completed before the next bucket brigade sequence begins. In other words the sum of the time delays provided by the time delay units33,34, . . . ,37,38and39is less than the duration of a PCP on line29as shown in FIG.8.

FIG. 6is a schematic block diagram of a single bit shows diagram of a type-D FF (flip-flop) register50of the kind shown inFIGS. 3A,3B, and4. On the rising edge of the CLOCK input on pipeline clock input line29, at time “t”, input data on input bus line28is captured and propagated to output bus lines60from FF register50. The FF register50is known in the art as a type D flip-flop. The FF register50comprises a first latch50′, a second latch50″, and an inverter70.

The latch50′ is connected to receive data from the input lines28at its data input D. The latch output L of the first latch50′ is connected by line28′ to the data input D of the second latch50″. The pipeline clock input line29is connected through inverter70to the clock input of the first latch50′, and the clock input of the second latch50″. When the pipeline clock signal on line29is low it causes the inverter70to provide a high output on line70′ to the clock input of the first latch50′, which latches data on bus line28. When the pipeline clock signal on line29is high it raises the clock input to the second latch50′ causing it to latch data on lines28′ from the output L of the first latch50′.

FIG. 7is a representative schematic diagram of the time delay unit33, which is identical to the other time delay units34, . . . ,37,38, and39of the type shown inFIG. 3. Atransition at the input, which is the pipeline clock line29, causes a like transition at the output of the delay unit33on line33′ after a time delay determined by various parameters known in the art, such as transistor size, voltage, and temperature. The time delay unit33comprises two inverters82and82″ connected in series. The pipeline clock line29is connected to the input of inverter82and the output of inverter82is connected by line82′ to the input of inverter82″. The output of the inverter82″ is supplied to the output line33′ of the time delay unit33. The delay provided by the time delay unit33is a function of the time required for the two inverters82/82″ to switch from low to high for inverter82and for the inverter82″ to switch from high to low.

FIG. 8is a timing diagram illustrating the sequence of events within the system ofFIGS. 3A,3B,4,5A and5B. It can be seen that the pipeline clock is a square wave that produces the FF output of data Djat time t. The clock29also generates narrow, latch clock pulses P1pulse on line42′ which produces the LNoutput of data Dj−N, at time t. Then the time delay unit DN−1generates a delayed clock signal on the line73generating a P2pulse on line43′ at time t+δ. The P2pulse on line43′ produces the LN−1 output of data Dj−N+1at time t+δ.

The stage3delayed clock signal on line77from time delay unit D3causes generation of a PN−2pulse on line47′ at time t+(N−3)δ, which produces the L3output on line63of data Dj−2, at that time. The stage2delayed clock signal on line78from the time delay unit D2causes generation of a PN−1pulse on the line48′ at time t+(N−2)δ, which produces the L2output on the line62of data Dj−1at that time.

Finally, the stage1delayed clock signal on line79from time delay unit D1causes generation of a PNpulse on line49′ at time t+(N−1)δ, which produces the L1output on line61of data Dj−, at that time.

This invention provides a significant area savings when the number of stages in the pipeline is greater than 2. For each additional stage, a single latch consumes approximately half the area of a conventional edge-triggered register. Also, there is no need to add scan ports to the latch bits, as they are already connected into a shift register.

The clock skew versus data path race condition is solved by design, using a regular structured array of latches and clock cells. The regularity of the logical structure allows the layout to be “compiled” (algorithmically generated) to any number of words times any number of bits.

As the number of words increases, however, the performance is degraded; the larger the number of words, the longer it takes to shift the words in the pipeline before the pipeline is ready to accept the next word. However, typical applications should allow 8-12 pipeline stages. If more pipeline stages were required than allowed by the application frequency, one would simply use another pipeline array, feeding the output data from one array directly into the input of the second array. Any number of arrays can be connected in such a manner to achieve any desired pipeline depth.

While this invention has been described in terms of the above specific embodiment(s), those skilled in the art will recognize that the invention can be practiced with modifications within the spirit and scope of the appended claims, i.e. that changes can be made in form and detail, without departing from the spirit and scope of the invention. Accordingly all such changes come within the purview of the present invention and the invention encompasses the subject matter of the following claims.