# US 11,308,025 B1 · State machine block for high-level synthesis > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,025 B1 - Document ID: US11308025B1 - Status: Granted - Kind: B1 - Application number: 16/946,154 - Filed: 2020-06-08 - Granted: 2022-04-19 - Earliest claimed: 2017-12-08 - Applicants: Stephen Melvin - Inventors: Shadi Assadikhomami; Tor Aamodt - Web page: https://patentgrep.com/patent/US11308025B1 ## CPC - G06F 15/7867: {with reconfigurable architecture} - G06F 15/80: comprising an array of processing units with common control, e.g. single instruction multiple data processors (G06F15/82 takes precedence {; for correlation function computation G06F17/15}) - G06F 9/44505: {Configuring for program initiating, e.g. using registry, configuration files} - Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE ## Abstract An architecture for a Field Programmable Gate Array (FPGA) that better supports the designs of finite state machines (FSMs) generated by High-Level Synthesis (HLS) tools. The architecture is based on categorizing states of a FSM into branch free path states and independent states. A memory unit stores next state information for independent states and an accumulator unit computes next state information for branch free path states. A control unit selects the next state based on either the memory unit or the accumulator unit. An input sequence encoder encodes external inputs and current state values into encoded sequence signals that are input to the memory unit. Also disclosed is a state assignment algorithm that assigns state values to states of the FSM by first identifying branch free paths that terminate on the same state and then eliminating overlap between paths. States along the same branch free path are assigned sequential values. ## Claims ### Claim 1 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein said accumulator unit determines a next state for the finite state machine when said current state value represents a state on a branch-free path of the finite state machine. ### Claim 2 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein said memory unit determines a next state for the finite state machine when said current state value represents a state that is not within a branch-free path of the finite state machine. ### Claim 3 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein said accumulator unit comprises an adder configured such that an increment by one is performed on said current state value to produce said accumulator unit next state value. ### Claim 4 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein said accumulator unit comprises one or more registers that store one or more of said state control signals. ### Claim 5 (depends on 4) The state machine block of claim 4 wherein said one or more registers comprise a branch target register. ### Claim 6 (depends on 4) The state machine block of claim 4 wherein said one or more registers comprise a path final state register. ### Claim 7 (depends on 4) The state machine block of claim 4 wherein said accumulator unit determines if said current state value represents a final state of a branch-free path of the finite state machine. ### Claim 8 (depends on 7) The state machine block of claim 7 wherein said one or more registers comprise a path final state register and said accumulator unit comprises a comparator that compares said current state value with the contents of said final state register. ### Claim 9 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein said control unit comprises a multiplexor that selects between said accumulator next state value and said memory unit next state value based on one or more of said state control signals. ### Claim 10 (depends on 9) The state machine block of claim 9 wherein said multiplexor selects between said accumulator next state value and said memory unit next state value based on a signal from said accumulator unit. ### Claim 11 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein said memory unit receives a proper subset of the bits of said current state value. ### Claim 12 (depends on 11) The state machine block of claim 11 wherein said proper subset comprises least significant bits of the current state value. ### Claim 13 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value; and a state decoder that receives said current state value and generates output signals. ### Claim 14 (depends on 13) The state machine block of claim 13 wherein said state decoder comprises a binary to one-hot decoder. ### Claim 15 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein one or more of the set consisting of said input sequence encoder, said memory unit, said arithmetic unit and said control unit is implemented within a specialized hard block within a field programmable gate array (FPGA). ### Claim 16 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein said memory unit, said arithmetic unit and said control unit are all implemented within a specialized hard block within a field programmable gate array (FPGA). ### Claim 17 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein one or more of the set consisting of said input sequence encoder, said memory unit, said arithmetic unit and said control unit is implemented using a hardware accelerator. ### Claim 18 A state machine block that implements a control path of a finite state machine comprising: a state register storing a current state value; an input sequence encoder that receives one or more external input signals and said current state value and generates one or more encoded sequence signals; a memory unit that receives said one or more encoded sequence signals and at least a portion of said current state value and generates a memory unit next state value and one or more state control signals; an accumulator unit that receives one or more of said state control signals and said current state value and is configured to perform an arithmetic operation on said current state value to generate an accumulator unit next state value; and a control unit that receives said memory unit next state value and said accumulator unit next state value and one or more of said state control signals and wherein said control unit determines a next state of the finite state machine based on either the accumulator next state value or the memory unit next state value, wherein one or more of the set consisting of said input sequence encoder, said memory unit, said arithmetic unit and said control unit is implemented using soft logic as part of a field programmable gate array (FPGA). ### Claim 19 (depends on 18) The state machine block of claim 18 wherein said soft logic is part of a look up table (LUT) based cluster. ### Claim 20 (depends on 18) The state machine block of claim 18 wherein said soft logic is part of a block RAM. ### Claim 21 A method of assigning state values in a finite state machine implemented in a state machine block with a memory unit that stores next state values for independent states and an accumulator unit that computes next state values for branch-free path states, the method comprising the steps of: identifying branch-free paths between each pair of divergent nodes; eliminating overlap by processing, for each divergent node d, each branch-free path terminating in node d to generate a new set of branch-free paths that have distinct states, wherein said step of eliminating identifies nodes in the finite state machine as being either memory unit nodes or arithmetic unit nodes; assigning state values such that nodes identified as memory unit nodes are numbered such that they are uniquely identified by a subset of state bits and nodes identified as arithmetic unit nodes are assigned sequential state values for states within the same branch-free path. ### Claim 22 (depends on 21) The method of claim 21 wherein said step of identifying comprises the steps of: putting all divergent nodes in a set D; putting all branch-free paths that start from a node in set D and end in another node in set D into a set P. ### Claim 23 (depends on 21) The method of claim 21 wherein said step of eliminating comprises the steps of: applying a path refinement algorithm on a set of branch-free paths to eliminate overlap of nodes on different branch-free paths by cutting one or more branch-free paths and labeling one or more nodes as independent nodes; identifying divergent nodes and independent nodes as memory unit nodes and identifying branch-free path nodes as arithmetic unit nodes. ### Claim 24 (depends on 21) The method of claim 21 wherein said step of assigning comprises the steps of: numbering all memory unit nodes such that a proper subset of state bits is sufficient to uniquely identify each memory unit node; numbering all arithmetic unit nodes consecutively such that nodes on the same branch-free path have their next state value one greater than their current value. ### Claim 25 (depends on 24) The method of claim 24 wherein said proper subset consist of a contiguous group of least significant state bits. ### Claim 26 (depends on 23) The method of claim 23 wherein said path refinement algorithm comprises the steps of: identifying a set of branch-free paths that all terminate in the same divergent node; sorting said set of branch-free paths based on their path length; traversing each path within said set of branch-free paths in order from a longest path to a shortest path by comparing each of its vertices to determine overlap with previously traversed paths; modifying said branch-free path such that overlap is eliminated. ### Claim 27 (depends on 26) The method of claim 26 wherein said step of modifying comprises the steps of: cutting an overlapping branch-free path so that it no longer overlaps any previously traversed paths; labeling a node where a cut was made as an independent node. ### Claim 28 (depends on 26) The method of claim 26 wherein said step of modifying comprises the steps of: replicating states in an overlapping branch-free path to eliminate overlap with any previously traversed paths. ### Claim 29 (depends on 23) The method of claim 23 wherein said step of assigning comprises the steps of: numbering memory unit nodes such that a proper subset of state bits is sufficient to uniquely identify each memory unit node; numbering arithmetic unit nodes consecutively such that nodes on the same branch-free path have their next state value one greater than their current value.