Method for Guaranteeing Correct Output of Non-Power of 2 Entry Register File
Original Publication Date: 2004-Aug-31
Included in the Prior Art Database: 2004-Aug-31
A method of guaranteeing correct output for non-power-of-2-entry register files is disclosed. If a typical decoder is used to decode the addresses of these family of register files, it is likely that some address combinations will not decode to a physical address. The solution shown in this article efficiently detects cases where an address would have caused floating outputs and ensures that the outputs do not float. Also, an efficient algorithm is given for the detector, which takes advantage of a special pattern that occurs when one tries to minimize the logic for the detect function. Finally, a method for saving further logic and time by sharing decoder logic with the detection logic is shown. The method can be implemented without significantly modifying typical register file design-concepts.
Method for Guaranteeing Correct Output of Non -Power of 2 Entry Register File
The problem of guaranteeing correct output for register files that are not a power 2 deep involves two steps: 1) efficiently recognizing the state of the register file when address combinations don't decode physical entries and 2) utilizing the signal in step 1 to directly drive the bitline with a determined value (1 or 0) instead of leaving it at an undriven state.
For the decoded n-bit input address, it needs a "greater than r detector", where "r" is used to represent the number of entries in the array. Whenever "n" is greater than "r", it requires to activate a signal represented by "d". By carefully selecting the way one can find "d" through an algorithm which will be described later. Also by considering the opportunity to share the logic of the normal address decoding portion of the register file, which will also be described in the next section, with this "greater than r detector" logic, one can save even more circuitry.
An easy way to design the "greater than r detector" is to use a general A>B comparator, with the A input of the comparator being the read address and the B input being the value of "r" in binary. It follows that the number of input bits needed in this comparator would be 2*n, where n is the number of bits in the address.
A better way of designing the "greater than r detector" would be to use the fact that the number of entries "r" is fixed and one can find a specific minimum function for this detector without having "r" in the equation. It needs the address bits A0A1...An, and then it can look for d r (A0,A1,..,An), saving the n-bits on the B input of the A>B comparator discussed above. There is a pattern to the minimum POS (product-of-sums) function for the d r (A0,A1,..,An) equations. This pattern allows to have a general algorithm for solving this minimum POS problem. The first entry of a group of d r 's for an n-bit address always starts with A0*(A1+A2+...+An). The last entry is always A0*A1*...*An. And the middle-most entry is always A0*A1. This is always the case, and one can keep on finding patterns for the "d r " equations between these known entries based on the previous group (e.g. second entry is A0*(A1+A2+...+An-1) and so forth).
Here is a quick description of this minimum POS algorithm: for a given "n", one can find
all of the "d r "s that correspond to those of previous "n" ("n-1").
1. The first half of the "d r "s of current "n", relate to each of the "d r "s of the previous "n". For each product term of dr of previous "n", the index of each address bit is incremented by one, and A1 is added to each of these product terms for every addresses after A0*. This provides the first half of the "d r "s for the current "n".
2. Similarly, the second half of the "d r "s of the current "n" (after the middle entry), relate to each of the "d r "s of the previous "n". For each product term of dr of previous "n", the index of each...