# US 9,519,860 B2 · Programmable device, hierarchical parallel machines, and methods for providing state information

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,519,860 B2
- Document ID: US9519860B2
- Status: Granted
- Kind: B2
- Application number: 14/293,338
- Filed: 2014-06-02
- Published: 2014-09-18
- Granted: 2016-12-13
- Earliest claimed: 2010-06-10
- Assignees: Micron Technology, Inc.
- Applicants: Micron Technology, Inc.
- Inventors: Paul Dlugosch
- Web page: https://patentgrep.com/patent/US9519860B2

## CPC

- G06F 9/544: {Buffers; Shared memory; Pipes}
- G06F 11/3024: {where the computing system component is a central processing unit [CPU]}
- G06F 11/3409: {for performance assessment}
- G06F 15/17312: {Routing techniques specific to parallel machines, e.g. wormhole, store and forward, shortest path problem congestion (routing on a LAN H04L45/00)}
- G06F 15/17362: {hierarchical topologies}
- G06F 15/825: {Dataflow computers}
- G06N 5/02: Knowledge representation; Symbolic representation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Programmable devices, hierarchical parallel machines and methods for providing state information are described. In one such programmable device, programmable elements are provided. The programmable elements are configured to implement one or more finite state machines. The programmable elements are configured to receive an N-digit input and provide a M-digit output as a function of the N-digit input. The M-digit output includes state information from less than all of the programmable elements. Other programmable devices, hierarchical parallel machines and methods are also disclosed.

## Claims

### Claim 1

A programmable device comprising:
a plurality of programmable elements, wherein the programmable elements are configured to implement one or more finite state machines, wherein the plurality of programmable elements are configured to receive a N-digit input and provide a M-digit output as a function of the N-digit input, wherein the M-digit output includes state information from less than all of the programmable elements.

### Claim 2 (depends on 1)

The programmable device of claim 1, wherein the plurality of programmable elements comprises one of two or more groups of programmable elements.

### Claim 3 (depends on 2)

The programmable device of claim 2, further comprising:
a N-digit input interface coupled to the one group of programmable elements and configured to receive the N-digit input; and
a M-digit output interface coupled to the one group of programmable elements and configured to provide the M-digit output.

### Claim 4 (depends on 2)

The programmable device of claim 2, wherein the one group of programmable elements comprises a block of programmable elements.

### Claim 5 (depends on 4)

The programmable device of claim 4, wherein the block of programmable elements comprises a plurality of rows of programmable elements, wherein each of the rows is coupled to a respective one of a plurality of intra-block switches.

### Claim 6 (depends on 5)

The programmable device of claim 5, wherein the programmable elements in each of the rows comprises:
a plurality of groups of two state machine elements; and
another programmable element.

### Claim 7 (depends on 2)

The programmable device of claim 2, further comprising:
a programmable switch configured to selectively couple the one group of programmable elements to another one of the groups of programmable elements, an input port, and/or an output port.

### Claim 8 (depends on 7)

The programmable device of claim 7, further comprising:
a register configured to store a program configured to program the plurality of programmable elements and the plurality of programmable switches.

### Claim 9 (depends on 1)

The programmable device of claim 1, wherein N equals M.

### Claim 10 (depends on 1)

The programmable device of claim 1, wherein M is an integer multiple of N.

### Claim 11 (depends on 1)

The programmable device of claim 1, further comprising:
OR logic configured to aggregate output from two or more of the programmable elements used to implement a same one of the finite state machines.

### Claim 12 (depends on 11)

The programmable device of claim 11, wherein the programmable elements are configured to implement a logical group of N state machines, wherein the outputs of the N state machines are aggregated to provide the M-digit output.

### Claim 13 (depends on 11)

The programmable device of claim 11, wherein the logic comprises an OR gate.

### Claim 14 (depends on 1)

The programmable device of claim 1, wherein the state information included in the M-digit output comprises compressed state information.

### Claim 15 (depends on 1)

The programmable device of claim 1, wherein the plurality of programmable elements comprise state machine elements.

### Claim 16 (depends on 1)

The programmable device of claim 1, wherein the M-digit output comprises a difference vector.

### Claim 17 (depends on 16)

The programmable device of claim 16, wherein each state in the implemented one or more finite state machines corresponds to a respective digit in a state vector, and wherein the difference vector includes only those digits in the state vector that change in response to an input symbol provided to the programmable device.

### Claim 18 (depends on 1)

The programmable device of claim 1, wherein each state in the implemented one or more finite state machines corresponds to a respective digit in a state vector, and wherein the M-digit output comprises only a subset of the digits in the state vector.

### Claim 19 (depends on 1)

The programmable device of claim 1, wherein the subset of the digits comprises those digits corresponding to final states in the one or more finite state machines.

### Claim 20 (depends on 1)

The programmable device of claim 1, wherein all state machines implemented in the device receive the N-digit input.

### Claim 21 (depends on 1)

The programmable device of claim 1, wherein the plurality of programmable elements comprise one of two or more groups of programmable elements, wherein each of the groups has its own dedicated input.

### Claim 22 (depends on 1)

The programmable device of claim 1, wherein the N-digit input is on a bottom of a semiconductor die, and wherein the M-digit output is on a top of the semiconductor die.

### Claim 23 (depends on 1)

The programmable device of claim 1, wherein the plurality of programmable elements comprise one of two or more groups of programmable elements, and wherein the programmable device is configured to provide state information from one of the groups to another one of the groups in the programmable device.

### Claim 24

A programmable device comprising:
a plurality of programmable elements wherein the programmable elements are configured to implement one or more finite state machines, wherein the plurality of programmable elements are configured to receive a N-digit input and provide a M-digit output as a function of the N-digit input, wherein the M-digit output is formed by compressing state information from each of the programmable elements.

### Claim 25 (depends on 24)

The programmable device of claim 24, wherein N equals M.

### Claim 26 (depends on 24)

The programmable device of claim 24, wherein M is an integer multiple of N.

### Claim 27 (depends on 24)

The programmable device of claim 24, further comprising:
logic configured to aggregate output from two or more of the programmable elements used to implement a same one of the finite state machines.

### Claim 28 (depends on 27)

The programmable device of claim 27, wherein the programmable elements are configured to implement a logical group of N state machines, wherein the outputs of the N state machines are aggregated to provide the M-digit output.