Concurrent processing produces fast priority selector

Itamar Elhanany, Ben-Gurion University, Beer-Sheva, Israel -- EDN, 4/13/2000

Priority-encoding circuits are common in high-speed digital applications, such as interrupt controllers and task schedulers, for selecting the highest priority set bit of all set bits in a given binary vector. Typically, the bit index corresponds to its priority level. A project required that several logic-function blocks, as opposed to one, would be enabled concurrently at any given time. Accordingly, the design goal was to identify the M highest priority admissible logic blocks. A conventional 1-bit priority selector receives as its input an arbitrary binary vector and outputs a vector of the same size, where the location of the set bit corresponds to the position of the highest priority set bit in the input vector. Such a selector may be described by the following Boolean expressions:

Figure 1 depicts a straightforward realization of an N-bit priority selector by means of cascading 1-bit priority selectors. Despite its simplicity, the design introduces extensive delay, which grows linearly with M.

An alternative implementation (Figure 2) is based on processing elements of the input vector concurrently as opposed to sequentially. The architecture comprises a bit-count function, which counts the number of set bits in its input vector, and a comparator. Parallel bit counts are deployed to concurrently determine the number of set bits in subsets of the input vector. A logical 1 at the comparator's output indicates that the bit count is smaller than or equal to M. The result is a binary mark signifying the range of bits in the input vector, which contains the M highest priority set bits. Note that, if N is the input vector length, then only N-M paths are necessary because the first M bits of the input vector contain by definition at most M set bits. You obtain the final output as a product of the input bits and the corresponding mask bits. The complexity of the bit-count function is O(logN); hence, the proposed scheme offers a high-speed invariant to M. (DI #2515)