High throughput finite state machine

In an FSM circuit, look-ahead-cascade modules are coupled to receive possible states and corresponding subsets of data inputs. Merge modules are coupled to a second-to-the-lowest to highest order of the look-ahead-cascade modules. The second-to-the-lowest to highest order of disambiguation modules are coupled to at least a portion of the merge modules. The lowest order of the disambiguation modules is coupled to the lowest order of the look-ahead-cascade modules. The lowest-to-highest order of the disambiguation modules are coupled to receive respective sets of interim states of rN states each to select respective sets of next states of r states each. A state register is coupled to receive a portion of the highest order of the sets of next states to provide a select signal. Each of the disambiguation modules is coupled to receive the select signal for selection of the sets of next states of the r states each.

TECHNICAL FIELD

The following description relates to integrated circuit devices (“ICs”). More particularly, the following description relates to a high-throughput finite state machine for an IC.

BACKGROUND

Various encoders, decoders, and other circuits use finite state machines (“FSMs”). Generally, an FSM makes a state transition sequentially for each data item input. For example, for a64B/66B encoder/decoder in an Ethernet Physical Coding Sublayer (“PCS”), a state transition is made for every 64-bit data block. For high throughput, wide data buses, such as for example 1280 bits (i.e., 20 64-bit data blocks), are used to process a large amount of data per clock cycle at high clock rate. In the past, this involved cascading multiple copies of the same FSM circuit so as to process multiple data blocks per clock cycle. However, the length of the critical path for state propagation is generally linearly increased, which offsets negatively the throughput increase in such cascaded FSM circuits. Accordingly, it has been problematic to meet a timing requirement in a 400 Gb/s PCS with a clock rate above 300 MHz.

Hence, it is desirable and useful to provide an FSM circuit that facilitates high data rates for meeting or exceeding high throughput of high-speed applications.

SUMMARY

An apparatus relates generally to a finite state machine circuit. In such an apparatus, look-ahead-cascade modules are coupled to receive possible states of the finite state machine circuit and coupled to receive data inputs, where the possible states include possible states P0through PN-1for N a positive integer greater than one, N representing a number of states in the finite state machine circuit. The look-ahead-cascade modules are coupled to receive corresponding subsets of the data inputs. Merge modules are coupled to a second-to-the-lowest order to the highest order of the look-ahead-cascade modules. A second-to-the-lowest order to the highest order of disambiguation modules are coupled to at least a portion of the merge modules. The lowest order of the disambiguation modules is coupled to the lowest order of the look-ahead-cascade modules. The lowest order to the highest order of the disambiguation modules are coupled to receive respective sets of interim states of rN states each to select respective sets of next states of r states each for r a positive integer greater than one. A state register is coupled to receive a portion of the highest order of the sets of next states for registration to provide a select signal, where each of the disambiguation modules is coupled to receive the select signal for selection of the sets of next states of the r states each.

A method relates generally to providing a finite state machine circuit. In such a method, a set of possible states and a set of data inputs are obtained for generation of look-ahead-cascade modules. The look-ahead modules are generated coupled to receive corresponding subsets of the set of data inputs and each is coupled to receive the set of possible states to provide first rN states from each of the look-ahead-cascade modules for r and N positive integers greater than one. The set of possible states includes possible states P0through PN-1. A pipelined tree is generated coupled to receive the first rN states from each of the look-ahead-cascade modules to provide corresponding second rN states. Disambiguation modules are generated coupled to the pipelined tree to receive the second rN states corresponding thereto to provide r states from each of the disambiguation modules. Each of the disambiguation modules is coupled to provide the r states therefrom from the second rN states corresponding thereto. A state register is generated coupled to receive a portion of the r states of the highest order of the disambiguation modules for registration thereof to provide a select signal. Each of the disambiguation modules is coupled to receive the select signal to select the r states for output corresponding thereto.

A method relates generally to operating a finite state machine. In such a method, a set of possible states is obtained by each look-ahead-cascade module of a parallelization of look-ahead-cascade modules. Non-overlapping subsets of data of a set of data are respectively received by the look-ahead-cascade modules from the lowest order to the highest order of the subsets of data. A first plurality of rN states, for r and N positive integers greater than one, is generated by each of the look-ahead-cascade modules from the subsets of data corresponding to the look-ahead-cascade modules for the set of possible states. The set of possible states includes possible states P0through PN-1. The first plurality of rN states from each of the look-ahead-cascade modules are input to a pipelined tree coupled to receive the first plurality of rN states from each of the look-ahead-cascade modules to merge states to provide a second plurality of rN states from the pipelined tree. The second plurality of rN states from the pipelined tree are input to disambiguation modules from the lowest order to the highest order of the second plurality of rN states to provide r states from each of the disambiguation modules. A portion of the r states of the highest order of the disambiguation modules is received for registration in a state register to provide a select signal therefrom. The select signal is provided to each of the disambiguation modules to select the r states for output of each of the r states corresponding thereto.

DETAILED DESCRIPTION

In the following description, numerous specific details are set forth to provide a more thorough description of the specific examples described herein. It should be apparent, however, to one skilled in the art, that one or more other examples and/or variations of these examples may be practiced without all the specific details given below. In other instances, well known features have not been described in detail so as not to obscure the description of the examples herein. For ease of illustration, the same number labels are used in different diagrams to refer to the same items; however, in alternative examples the items may be different.

Before describing the examples illustratively depicted in the several figures, a general introduction is provided to further understanding.

As described below in additional detail, a scalable finite state machine (“FSM”) parallelization with divided and concurrent processing may be used for high data rates, such as from 400 Gb/s upwards, using a wide, though divided out, data bus with a large input width, such as 1000-bits and beyond, for clock rates of 300 MHz and beyond. Such an FSM architecture may be used with a small-to-moderate number of states, which is common in many various encoders, decoders, and other applications. For example, a 400 Gb/s PCS64b/66bencoder or decoder may be implemented using an FSM circuit as described below herein with an input data bus width of 1280 bits for 20 blocks of 64 bit data per clock cycle processing for a clock rate of at least 300 MHz. For an IEEE 802.3 specification, the FSM of PCS64b/66bencoder or decoder contains five states for one transition per 64-bit block. This is just one example application, and there are many other applications that may use an FSM circuit as described herein. Furthermore, because an FSM architecture as described herein is modular and configurable, various resource-performance trade-offs may be used to adapt to an application for implementation of an FSM circuit.

With the above general understanding borne in mind, various configurations for FSM architectures are generally described below.

FIG. 1is a block diagram depicting an exemplary finite state machine (“FSM”) architecture100with a binary merger. FSM architecture or FSM circuit100may have a latency associated with O(r+log2(m/r)) and a resource usage associated with O(m log 2(m/r)), where m and r are positive integers greater than one and where “O” is for what is known as a “Big O” notation in mathematics. FSM architecture100may be implemented in an FSM circuit, as described below in additional detail. In the following description, m is a number of data inputs. Look-ahead results for data inputs Di, Di+1, . . . , Dj-1, Djmay be denoted by L(i,j). For a single-clock cycle150combining function f, look-ahead results for m data inputs may be expressed for example as L(0, m−1)=f(L(0,(m/2)−1), L(m/2, m−1)). Thus, all of FSM architecture100may be in a single clock domain150, namely all registers of FSM architecture100may be clocked with a same clock signal150.

Along the above lines, FSM architecture100includes look-ahead-cascade modules102coupled to receive possible states, such as a set of possible states109and data or a set of data inputs or data101. The set of possible states, which may be initial states, may include possible states P0through PN-1for N a positive integer greater than one. Possible states109may be the same for all of subsets of data101. Data101may be subdivided into non-overlapping subsets. Possible states P0through PN-1may be respective constants. In this example, there are eight subsets of data101, namely subsets D101-0through D101-7. There may be fewer or more subsets of data in other implementations.

For a data bus consisting of m data items each of which is w bits, data101may be designated as D0through Dm-1, where the width of Di (i=0, 1, . . . , m−1) is w bits. Such subsets D101-0through D101-7therefore may correspond to groupings of sequential bits of data. Look-ahead-cascade modules102-0through102-7are coupled to receive corresponding subsets D101-0through D101-7of data. For example, a subset of data Dm-rthrough Dm-1may be provided to the highest order look-ahead-cascade module102, which in this example is look-ahead-cascade module102-7. The lowest order look-ahead-cascade module, which in this example is look-ahead-cascade module102-0, may be provided with a subset of data D0through Dr-1. Merge modules103may be respectively coupled to a second-to-the-lowest order to the highest order of look-ahead-cascade modules102, namely look-ahead-cascade modules102-1through102-7in this example.

Along the above lines, data101may have a width W=m*w, for W an integer substantially greater than 100 and for m a positive integer substantially greater than 10 for example. Data101includes data items D0through Dm-1. The number of look-ahead-cascade modules102may be equal to m/r, which is equal to the number of subsets of data101. Each of these subsets may include r data items in sequence selected from data items D0through Dm-1. Subsets of data101may be contiguous and non-overlapping with respect to one another.

Merge modules103may be coupled to form a network to merge states from multiple look-ahead-cascade modules, namely a pipelined tree110. As described below in additional detail, a merging network, which may be pipelined tree110, includes a number of merging nodes, which may be provided by merge modules103. Each such merging or merge node may perform a cross-product to merge two sets of states. As described below in additional detail, a merging node may be implemented using multiple multiplexers.

In this example, pipelined tree110is a binary merge tree having a latency associated with O(r+log2(m/r)) and a resource usage associated with O(m log2(m/r)). More generally, merging latency for pipelined tree110may be O(log(m)), whereas the resource usage is O(m·log(m)), for m state transitions per cycle. Registers, as well as clock signals, for pipelined tree110are not illustratively depicted for purposes of clarity and not limitation. However, in this example, there may be three register or pipeline stages113through115.

For pipelined tree110ofFIG. 1, there are m/r lanes, where for each of such lanes r groups of N states each, namely rN states113-0through113-7, are respectively output from look-ahead-cascade modules102-0through102-7onto such m/r lanes. For rN states113-1through113-7, each set of rN states is provided to a corresponding merge module103. For rN states113-0output from the lowest order look-ahead-cascade module102-0, such states are directly coupled to the lowest order disambiguation module104-0of disambiguation modules104. However, these rN states113-0may be pipelined through pipelined stages113through115labeled respectively as rN states114-0,115-0, and116-0for correspondence with other rN states, as described below in additional detail.

For pipeline stage113, the highest order N states of each of rN states113-0,113-2,113-4, and113-6are provided as selectors111-0,111-2,111-4, and111-6, respectively, to a corresponding order-adjacent nearest neighbor merge module103on a next level order higher than a level on which rN states113-0,113-2,113-4, and113-6are located. Along those lines, N states111-0,111-2,111-4, and111-6are selectors for next level higher order corresponding rN states113-1,113-3,113-5, and113-7of respective merge modules103for a pipeline stage113. From each of merge modules103in pipeline stage113, corresponding rN states114-1,114-3,114-5, and114-7are selected for output from such merge modules103respectively using N states111-0,111-2,111-4, and111-6, as selectors. For example, a set of rN states113-3, which are interim states, are input to a merge module103of a same order or level, and the highest order N states of interim rN states113-2are provided to such merge module103as selectors to select interim rN states114-3which are input to a next merge module103of the same order or level.

In pipeline stage114, rN states114-0through114-7are further processed for a binary or binary-like merge in pipelined tree110. Along those lines, rN states114-0and114-1are piped through such pipeline stage114, with the highest order N states111-1of rN states114-1being provided as selectors to a merge module103on a next higher order level than rN states114-1. Pipelined rN states114-1may be pipelined through pipelined stages114and115labeled respectively as rN states115-1and116-1for correspondence with other rN states, as described below in additional detail.

For pipelined stage114, rN states114-2,114-3,114-6, and114-7are input to corresponding merge modules103with the highest order N states111-1and111-5respectively of rN states114-1and114-5provided as selectors. More particularly, N states111-1are provided to two merge modules respectively coupled to receive rN states114-2and114-3to respectively select therefrom rN states115-2and115-3. There is a merge module103coupled to receive rN states114-2at a next higher order than rN states114-1, from which N states111-1are obtained as selectors, and there is a merge module103coupled to receive rN states114-3, to which N states111-1are provided, at a next higher order than rN states114-2. Likewise, there is a merge module103coupled to receive rN states114-6at a next higher order than rN states114-5, from which N states111-5are obtained as selectors, and there is a merge module103coupled to receive rN states114-7, to which N states111-5are provided, at a next higher order than rN states114-6. Thus, N states111-1and111-5are each provided to an order-adjacent nearest neighbor level merge module103and to a merge module103one level above such an order-adjacent nearest neighbor level merge module103. Generally, N states111-1and111-5are provided to sets of merge modules103. More particularly, N states111-1are provided one level higher to an order-adjacent nearest neighbor merge module103and are provided two levels higher to a merge module103that is not an order-adjacent nearest neighbor. Likewise, N states111-5are provided one level higher to an order-adjacent nearest neighbor merge module103and are provided two levels higher to a merge module103that is not an order-adjacent nearest neighbor.

For pipelined stage115, rN states115-0through115-3may be pipelined through, with the highest order N states111-3obtained from rN states115-3being used as selectors. Along those lines, rN states115-0through115-3corresponding to the lowest to fourth order may be pipelined through pipelined stage115labeled respectively as rN states116-0through116-3for correspondence with other rN states, as described below in additional detail.

In pipelined stage115, rN states115-4through115-7, corresponding to a fifth to eight (highest) order are input to respective merge modules103on corresponding levels for selection of rN states116-4through116-7, respectively, responsive to rN states111-3. Thus, rN states111-3may be provided from a fourth order or level up to each of the fifth through eighth levels of pipelined tree110.

From pipelined tree110, interim rN states116-0through116-7from the lowest to the highest order are provided to corresponding disambiguation modules104-0through104-7of disambiguation modules104. Thus, a second-to-the-lowest order to the highest order of disambiguation modules104are coupled to at least a portion of merge modules103of pipelined tree110. The lowest order disambiguation module104-0of disambiguation modules104is coupled to the lowest order look-ahead-cascade module102-0of look-ahead-cascade modules102through register stages113through115of pipelined tree110without going through any merge module103of pipelined tree110.

The lowest order to the highest order of disambiguation modules104-0through104-7, respectively, are coupled to receive respective sets of interim states of rN states116-0through116-7, where each of disambiguation modules104-0through104-7is to select respective sets of next states129-0through129-7of r states each. Each of next states129-0through129-7may be provided to a corresponding data register105for subsequent output. Data registers105may thus be respectively coupled to outputs of disambiguation modules104to receive and register the m/r sets of next states output of r states each respectively output from disambiguation modules104-0through104-7.

A state register106may be coupled to receive the highest order state of a set of next states, namely a portion of next states129-7in this example, for registration of a current state select signal107to output from state register106as a next state select signal108. Each of disambiguation modules104-0through104-7may be coupled to receive next state select signal108for selection of sets of next states129-0through129-7of r states each. For example, if N is equal to 8, then next state select signal108may be three bits wide, namely 23, to select one set of r states out of rN states.

From the above-description, it should be understood that parallel state merging is used instead of conventional sequential state propagation. Thus, overall latency may be reduced, i.e., to r+log 2(m/r) for r a small constant, with no increase in critical path length as compared with a conventional FSM circuit. As described below in additional detail, look-ahead-cascade modules use a “divide-and-conquer” approach by dividing a set of data into subsets and processing each of the subsets of data in parallel. Additionally, each possible outcome is determined in parallel to provide a look-ahead result to reduce timing overhead. Along those lines, length of the critical path of an FSM architecture is reduced to O(1), namely equivalent or comparable to a conventional FSM circuit, while resources may be O(m·log(m)) and latency may be O(log(m)) for FSM architecture100processing m data blocks per clock cycle. FSM architecture100is a modular architecture, which may be used for parallelization to scale up to address an application. Such modularity and scalability may be useful in applications where an FSM circuit may be programmed according to an application, such as in an FPGA or other integrated circuit with programmable resources. FSM architecture100may thus have a high throughput facilitated in part by a wide data bus with an ability to sustain a high clock rate.

FIG. 2is a block diagram depicting an exemplary look-ahead-cascade module102-0for FSM architecture100ofFIG. 1. As each of look-ahead-cascade modules102has a same configuration, a look-ahead-cascade module102-0of FSM architecture100is used as an example representing each of such look-ahead-cascade modules102, for purposes of clarity and not limitation, as only the data inputs change from one look-ahead-cascade module102to another look-ahead-cascade module102.

Look-ahead-cascade module102-0includes N sets of transaction, T, blocks201-0through201-(r−1) coupled in series for sequential and parallel processing. T blocks201-0through201-(r−1) may be implemented using combinational logic, where each of T blocks201-0through201-(r−1) may collectively use one clock cycle of a clock signal, not shown for purposes of clarity and not limitation.

Each of possible states109-0through109-(N−1) for N possible states109, namely possible states P0through PN-1, are respectively provided to N×T blocks201-0. Each series of T blocks201-0through201-(r−1) are respectively coupled to receive data items D0through Dr-1of data subset101-0, where data items D0through Dr-1of data subset101-0are respectively provided to T blocks201-0through201-(r−1) for each row or series. Outputs of each of T blocks201-0through201-(r−1) for each series are provided for output as rN states113-0. Each T block201may thus trigger a state transition, where each such state transition may depend on a prior possible state or a prior data state transition. Thus, there are r outputs for each series and N series for a total of rN states output from look-ahead-cascade module102-0, where a highest order of N states of such rN states output are from a series with a possible state PN-1input, and the lowest order of N states of such rN states output are from a series with a possible state P0input. Each rN states of a plurality of rN states113may be registered in registers, not illustratively depicted for purposes of clarity, before being piped into a downstream pipelined tree described below in additional detail for merging data states.

Accordingly, by dividing data into subsets of r items and processing each subset in parallel with each other subset of data less time is consumed. In other words, each chain of r T blocks is still shorter for a subset of a set of data than for the entire set of data, which facilitates processing data through a look-ahead-cascade module in a single clock cycle. Additionally, all possible combinations of such data, namely for all N possible states, may be processed in parallel to provide a look-ahead result for selection to reduce timing overhead. These reductions in timing overhead may facilitate use of a higher frequency of operation, as well as a reduction in latency. Furthermore, the highest order of N states of rN states of a lower order look-ahead-cascade module may be used to select rN states of a higher order look-ahead-cascade module, as described below in additional detail.

FIG. 3is a block diagram depicting an exemplary merge module103for FSM architecture100ofFIG. 1. As each merge module103has a same configuration, a merge module103of pipelined tree110is described for purposes of clarity and not limitation.

Merge module103includes r merge blocks103-0through103-(r−1). Merge blocks103-0through103-(r−1) are respectively coupled to receive N states317-0through317-(r−1) of rN states113-7. N states111-6are provided to each of merge blocks103-0through103-(r−1) as selectors, such as multiplexer control select signals for example or other control signals provided to select circuits. N states111-6may be the highest order of rN states113-6. A remaining (r−1)N states316of rN states113-6, as well as N states111-6may be pipelined forward as rN states114-6. Merge blocks103-0through103-(r−1) respectively output N states327-0through327-(r−1). N states327-0through327-(r−1) collectively are rN states114-7.

FIG. 4is a schematic diagram depicting an exemplary merge block103-(r−1) for merge module103ofFIG. 3. As each merge block of merge module103has a same configuration, a merge block103-(r−1) of pipelined tree110is described for purposes of clarity and not limitation.

Merge block103-(r−1) is coupled to receive N states317-(r−1) from which N states327-(r−1) are selected using N states111-6as select signals. More particularly, N states111-6are provided as select signals S0through SN-1to corresponding multiplexers401-0through401-(N−1) of merge block103-(r−1) of merge module103ofFIG. 3.

N states317-(r−1) are input to each of multiplexers401-0through401-(N−1). Select signals S0through SN-1, from lowest to highest order, respectively provided to multiplexers401-0through401-(N−1), from lowest to highest order, are used to select corresponding multiplexer outputs402-0through402-(N−1) respectively from multiplexers401-0through401-(N−1). Multiplexer outputs402-0through402-(N−1) collectively provide N states327-(r−1).

FIG. 5is a schematic diagram depicting an exemplary disambiguation module104-7for FSM architecture100ofFIG. 1. As each disambiguation module of FSM architecture100has a same configuration, a disambiguation module104-7is described for purposes of clarity and not limitation.

Disambiguation module104-7is coupled to receive rN states116-7to provide r states129-7. Disambiguation module104-7is coupled to receive a select signal108, which select signal108is provided to each of multiplexers504-0through504-(r−1) of disambiguation module104-7as a control select signal. Each of multiplexers504-0through504-(r−1) of disambiguation module104-7is respectively coupled to receive N states517-0through517-(r−1), from lowest to highest order, to select multiplexer outputs, namely output next states527-0through527-(r−1) respectively, therefrom. Multiplexer output next states527-0through527-(r−1) collectively provide r states129-7.

A highest or most significant bits portion of output next state527-(r−1) may be used to provide a current state select signal107for registration as previously described. Current state select signal107has a size or bit width of log(N). Along those lines, each of r states109-0through109-7respectively output from each of disambiguation modules104-0through104-7has a bus width of r multiplied by log(N).

FIG. 6is a block diagram depicting an exemplary FSM architecture100with a linear merger. Pipelined tree110of FSM architecture100ofFIG. 6is a linear merger tree having a latency associated with O(m) and a resource usage associated with O(m) for m state transitions per cycle. As only pipelined tree110of FSM architecture100ofFIG. 6is different than that ofFIG. 1, generally only pipelined tree110of FSM architecture100ofFIG. 6is described below for purposes of clarity and not limitation.

In this example, merge modules103-1through103-7may respectively be coupled between look-ahead-cascade modules102-1through102-7and corresponding disambiguation modules104-1through104-7for pipelined tree110. Look-ahead-cascade modules102-0and disambiguation module104-0may be coupled to one another as previously described for pipelined tree110. However, in this example of a pipelined tree110there may be pipelined stages113through119, namely a longer latency with fewer merge modules103than pipelined tree110ofFIG. 1.

N states111-0through111-6may respectively be provided in pipelined stages113through119to a nearest neighbor merge module103one level or order higher for respective selection of rN states. More particularly, rN states113-1through113-7are respectively input to corresponding merge modules103-1through103-7of same order for selection of rN states120-1through120-7, respectively, for being pipelined out of pipeline tree110, and rN states113-0are more directly pipelined out of pipeline tree110. Such rN states120-1through120-7may effectively be selected responsive to N states111-0through111-6, respectively, provided as selectors to merge modules103-1through103-7in pipeline stages113through119, respectively.

FIG. 7is a block diagram depicting an exemplary FSM architecture100with a hybrid linear-binary merger. Pipelined tree110of FSM architecture100ofFIG. 7is a hybrid linear-binary merger tree, namely a hybrid of pipelined trees110of FSM architectures100ofFIGS. 1 and 6. As only pipelined tree110of FSM architecture100ofFIG. 7is different than that ofFIGS. 1 and 6, generally only pipelined tree110of FSM architecture100ofFIG. 7is described below for purposes of clarity and not limitation.

In this example, a linear portion of pipelined tree110may have merge modules103-1through103-4respectively coupled between look-ahead-cascade modules102-1through102-4and corresponding disambiguation modules104-1through104-4, with look-ahead-cascade modules102-0and disambiguation module104-0coupled to one another as previously described. This linear portion spans pipelined stages113through116. Furthermore, a linear portion of pipelined tree110may have first instances of merge modules103-5through103-7respectively coupled to look-ahead-cascade modules102-5through102-7spanning pipelined stages113through115. In a binary portion of pipelined tree110, second instances of merge modules103-5through103-7are respectively coupled to outputs of first instances of merge modules103-5through103-7for pipelined stage116. In this example of a pipelined tree110there may be pipelined stages113through116, namely a longer latency with fewer merge modules103than pipelined tree110ofFIG. 1but a shorter latency with more merge modules103than pipelined tree110ofFIG. 6.

N states111-0through111-3may respectively be provided in pipelined stages113through116to a nearest neighbor merge module103one level or order higher for respective selection of rN states, and N states111-4through111-6may respectively be provided in pipelined stages113through115to a first instance nearest neighbor merge module103one level or order higher for respective selection of rN states. More particularly, rN states113-1through113-4are respectively input to corresponding merge modules103-1through103-4of same order for selection of rN states117-1through117-4, respectively, pipelined out of pipeline tree110. Such rN states117-1through117-4may effectively be selected responsive to N states111-0through111-3, respectively, provided as selectors to merge modules103-1through103-4in pipeline stages113through119, respectively. Additionally, rN states113-5through113-7are respectively input to first instances of corresponding merge modules103-5through103-7of same order in a linear portion, and rN states output from first instances of merge modules103-5through103-7are respectively provided as inputs to second instances of merge modules103-5through103-7of same order for selection of rN states117-5through117-7, respectively, pipelined out of pipeline tree110. Such rN states117-5through117-7may be selected in a binary portion of pipelined tree110responsive to N states111-3provided as selectors to each of such second instances of merge modules103-5through103-7in pipeline stage116.

FIG. 8is a flow diagram depicting an exemplary FSM configuration flow800to provide any of FSM architectures100previously described. FSM architecture100may be instantiated in a programmable device, such as an FPGA or other programmable device.

At801, a set of possible states and a set of data inputs may be obtained for generation of look-ahead-cascade modules. At802, such look-ahead modules may be generated coupled to receive corresponding subsets of the set of data inputs and each coupled to receive the set of possible states to provide first rN states from each of the look-ahead-cascade modules for r and N positive integers greater than one. Such set of possible states may include possible states P0through PN-1. Such first rN states may be rN states113-0through113-7for example.

At803, a pipelined tree may be generated coupled to receive the first rN states from each of the look-ahead-cascade modules to provide corresponding second rN states. Such pipelined tree may be a binary tree, a linear tree, or hybrid linear-binary tree, and thus for example such second rN states may be rN states116-0through116-7,120-0through120-7, or117-0through117-7, respectively.

At804, disambiguation modules may be generated coupled to the pipelined tree to receive the second rN states corresponding thereto to provide r states from each of the disambiguation modules. Each of the disambiguation modules may be coupled to provide the r states respectively therefrom from the second rN states corresponding thereto.

At805, a state register may be generated, or instantiated, coupled to receive a portion of the r states of the highest order of the disambiguation modules for registration thereof to provide a select signal. At806, each of the disambiguation modules may be coupled to receive the select signal to select the r states for output corresponding thereto. Such select signal may be used to select r states for output from each corresponding rN states input to such disambiguation modules generated.

FIGS. 12-1through12-3is a listing diagram depicting an exemplary FSM configuration flow1200for FSM architecture100ofFIG. 1. FSM configuration flow1200is a pseudo-code listing for instantiating an FSM architecture100ofFIG. 1. However, other configuration flows for instantiating any of the FSM architectures100described herein or variations thereof with respect to a merge network follow from the description hereof.

InFIGS. 12-1through12-3, “D” is short for input data; “MM” is short for merge module; “DM” is short for disambiguation module; “L+C” is short for look-ahead-cascade module; “Sigma [N]” represents N possible states; and “Delta” is short for a transition function. This and other information in FSM configuration flow1200follows from the above description.

InFIG. 12-1, a parallelization (“par”) is generated at1202for m outputs or results at1203by incrementing i for result[i] based on history[i, (int)s0)] for disambiguation modules.FIG. 12-2lists a detailed breakout of history=doSteps (Sigma, m, D) at1201inFIG. 12-1. Generally, “history1” and “history2” are for partitioning of data states into different groups, and “history” is for merging history1 and history2. Along those lines,FIG. 12-2is generally for constructing a merge network.FIG. 12-3is generally for constructing look-ahead-cascade modules.

FIG. 9is a flow diagram depicting an exemplary FSM operational flow900for FSM architecture100ofFIG. 1,6, or7. At901, a set of possible states may be obtained by each look-ahead-cascade module of a parallelization of look-ahead-cascade modules. At902, non-overlapping subsets of data of a set of data may be respectively received by the look-ahead-cascade modules from the lowest order to the highest order of the subsets of data. At903, a first plurality of rN states, for r and N positive integers greater than one, may be generated by each of the look-ahead-cascade modules from the subsets of data corresponding to the look-ahead-cascade modules for the set of possible states, where the set of possible states includes possible states P0through PN-1.

At904, the first plurality of rN states from each of the look-ahead-cascade modules may be input to a pipelined tree coupled to receive the first plurality of rN states from each of the look-ahead-cascade modules to merge states to provide a second plurality of rN states from the pipelined tree. At905, the second plurality of rN states from the pipelined tree may be input to disambiguation modules from the lowest order to the highest order of the second plurality of rN states to provide r states from each of the disambiguation modules. At906, a portion of the r states of the highest order of the disambiguation modules may be received for registration in a state register to provide a select signal from the state register. At907, each of the disambiguation modules may be provided with the select signal to select the r states for output of each of the r states corresponding to the disambiguation modules.

Because one or more of the examples described herein may be implemented in an FPGA, a detailed description of such an IC is provided. However, it should be understood that other types of ICs may benefit from the technology described herein.

Each programmable tile typically includes both programmable interconnect and programmable logic. The programmable interconnect typically includes a large number of interconnect lines of varying lengths interconnected by programmable interconnect points (“PIPs”). The programmable logic implements the logic of a user design using programmable elements that can include, for example, function generators, registers, arithmetic logic, and so forth.

Another type of PLD is the Complex Programmable Logic Device, or CPLD. A CPLD includes two or more “function blocks” connected together and to input/output (“I/O”) resources by an interconnect switch matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays (“PLAs”) and Programmable Array Logic (“PAL”) devices. In CPLDs, configuration data is typically stored on-chip in non-volatile memory. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration (programming) sequence.

As noted above, advanced FPGAs can include several different types of programmable logic blocks in the array. For example,FIG. 10illustrates an FPGA architecture1000that includes a large number of different programmable tiles including multi-gigabit transceivers (“MGTs”)1001, configurable logic blocks (“CLBs”)1002, random access memory blocks (“BRAMs”)1003, input/output blocks (“IOBs”)1004, configuration and clocking logic (“CONFIG/CLOCKS”)1005, digital signal processing blocks (“DSPs”)1006, specialized input/output blocks (“I/O”)1007(e.g., configuration ports and clock ports), and other programmable logic1008such as digital clock managers, analog-to-digital converters, system monitoring logic, and so forth. Some FPGAs also include dedicated processor blocks (“PROC”)1010.

For example, a CLB1002can include a configurable logic element (“CLE”)1012that can be programmed to implement user logic plus a single programmable interconnect element (“INT”)1011. A BRAM1003can include a BRAM logic element (“BRL”)1013in addition to one or more programmable interconnect elements. Typically, the number of interconnect elements included in a tile depends on the height of the tile. In the pictured embodiment, a BRAM tile has the same height as five CLBs, but other numbers (e.g., four) can also be used. A DSP tile1006can include a DSP logic element (“DSPL”)1014in addition to an appropriate number of programmable interconnect elements. An IOB1004can include, for example, two instances of an input/output logic element (“IOL”)1015in addition to one instance of the programmable interconnect element1011. As will be clear to those of skill in the art, the actual I/O pads connected, for example, to the I/O logic element1015typically are not confined to the area of the input/output logic element1015.

Some FPGAs utilizing the architecture illustrated inFIG. 10include additional logic blocks that disrupt the regular columnar structure making up a large part of the FPGA. The additional logic blocks can be programmable blocks and/or dedicated logic. For example, processor block1010spans several columns of CLBs and BRAMs.

FIG. 11is a block diagram depicting an exemplary computer system1100. Computer system1100may include a programmed computer1110coupled to one or more display devices1101, such as Cathode Ray Tube (“CRT”) displays, plasma displays, Liquid Crystal Displays (“LCD”), projectors and to one or more input devices1106, such as a keyboard and a cursor pointing device. Other known configurations of a computer system may be used. Computer system1100by itself or networked with one or more other computer systems1100may provide an information handling system.

Programmed computer1110may be programmed with a known operating system, which may be Mac OS, Java Virtual Machine, Real-Time OS Linux, Solaris, iOS, Android Linux-based OS, Unix, or a Windows operating system, among other known platforms. Programmed computer1110includes a central processing unit (CPU)1104, memory1105, and an input/output (“I/O”) interface1102. CPU1104may be a type of microprocessor known in the art, such as available from IBM, Intel, ARM, and Advanced Micro Devices for example. Support circuits (not shown) may include cache, power supplies, clock circuits, data registers, and the like. Memory1105may be directly coupled to CPU1104or coupled through I/O interface1102. At least a portion of an operating system may be disposed in memory1105. Memory1105may include one or more of the following: flash memory, random access memory, read only memory, magneto-resistive read/write memory, optical read/write memory, cache memory, magnetic read/write memory, and the like, as well as non-transitory signal-bearing media as described below.

I/O interface1102may include chip set chips, graphics processors, and/or daughter cards, among other known circuits. An example of a daughter card may include a network interface card (“NIC”), a display interface card, a modem card, and a Universal Serial Bus (“USB”) interface card, among other known circuits. Thus, I/O interface1102may be coupled to a conventional keyboard, network, mouse, display printer, and interface circuitry adapted to receive and transmit data, such as data files and the like. Programmed computer1110may be coupled to a number of client computers, server computers, or any combination thereof via a conventional network infrastructure, such as a company's Intranet and/or the Internet, for example, allowing distributed use for interface generation.

Memory1105may store all or portions of one or more programs or data to implement processes in accordance with one or more embodiments hereof to provide program product1120. Thus for example, FSM configuration flow1200ofFIGS. 12-1through12-3may be implemented as a program product1120, which when used in a programmed computer for configuration of an FPGA may be used to generate a configuration stream for instantiating an FSM architecture100in an FPGA. Additionally, those skilled in the art will appreciate that one or more embodiments hereof may be implemented in hardware, software, or a combination of hardware and software. Such implementations may include a number of processors or processor cores independently executing various programs and dedicated hardware or programmable hardware.

One or more program(s) of program product1120, as well as documents thereof, may define functions of embodiments hereof and can be contained on a variety of non-transitory signal-bearing media, such as computer-readable media having code, which include, but are not limited to: (i) information permanently stored on non-writable storage media (e.g., read-only memory devices within a computer such as CD-ROM or DVD-ROM disks readable by a CD-ROM drive or a DVD drive); or (ii) alterable information stored on writable storage media (e.g., floppy disks within a diskette drive or flash drive or hard-disk drive or read/writable CD or read/writable DVD). The above embodiments specifically include information downloaded from the Internet and other networks. Such non-transitory signal-bearing media, when carrying computer-readable instructions that direct functions hereof, represent embodiments hereof.

While the foregoing describes exemplary apparatus(es) and/or method(s), other and further examples in accordance with the one or more aspects described herein may be devised without departing from the scope hereof, which is determined by the claims that follow and equivalents thereof. Claims listing steps do not imply any order of the steps. Trademarks are the property of their respective owners.