Asynchronous clock-less digital logic path planning apparatus and method
Inventors
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-10719079-B2
Publication Date
2020-07-21
Expiration Date
Abstract
A hybrid of initial time consuming phase of a Single Directional Dijkstra's Algorithm is embodied on an unclocked CMOS logic chip using a parallelized approach with Asynchronous Digital Logic (ADL). The chip includes a a plurality of addressable configurable cells arranged as a multidimensional orthogonal array. The cell array only executes mathematical operations based on a communication between immediately adjacent cells.
Core Innovation
The invention is an asynchronous, reconfigurable, clock-less CMOS path-planning co-processor comprising a multidimensional orthogonal array of addressable configurable cells that execute arithmetical operations. The cell array core implements a Single-Directional Dijkstra Algorithm (SDDA) variant in which cells exchange arithmetic data only with immediately adjacent neighbors through input/output (I/O) couplings and cell-to-cell interconnection via data buses and control lines. The array propagates lowest accumulated distance values without a use of any clock, using asynchronous behavior.
Each cell includes a plurality of input adders, numeric comparators, orthogonal and diagonal input value registers, and an output value register. Circuitry includes an AND gate and comparator structures that receive data from input adders and produce lowest values that are used to update the cell output value register. The architecture uses gated latch memory elements and output conditioning buffers such that cell operations proceed asynchronously while exchanging values with adjacent cells.
Per-cell local WeightLength parameters, including map-based PBP/terrain undesirability, are written into the orthogonal and diagonal registers via a 16-bit array register bus, and lowest accumulated distance values are asynchronously propagated through the array. The co-processor supports start-cell behavior and operational modes including initialization/reset, setup/run, and read-results, and it provides result readout using a tri-state global register bus and completion detection options using current draw sensing/comparator outputs to a controller interrupt.
Claims Coverage
The independent claims are clm-00001, clm-00009, and clm-00014, each centered on an asynchronous, clock-less, reconfigurable cell array core with adjacent-cell value propagation and bus/control-line connectivity. Across the independent claims, there are three inventive features focused on cell circuitry, the co-processor interface, and the orthogonal array topology.
Asynchronous clock-less reconfigurable orthogonal cell array with adjacent 16-bit register and bus interconnections
A plurality of addressable configurable cells arranged as a multidimensional orthogonal array, each cell comprising a cell I/O interface where each cell input connects to one immediately adjacent cell output; a cell data register bus interface and a plurality of cell data register buses; a cell value select control line; array-wide read/write and reset/run control line(s) and a cell value array selection control line; a 16-bit array register bus; and a 14-bit array address bus with row address selection control lines and column address selection control lines; the interconnected plurality of addressable configurable cells configured to process asynchronously and without a use of any clock the data transmitted by the plurality of data buses and the plurality of I/O connections.
Cell-level minima propagation using input adders and cascaded comparators
Each cell includes a plurality of 16-bit input adders, four first data comparators in a 16-bit register connection with two input adders each, two second data comparators in a 16-bit register connection with two first data comparators each, and a third data comparator in a 16-bit register connection with the two second data comparators, together with an orthogonal input value register, a diagonal input value register, and an output value register; an AND gate outputs to the orthogonal input value register, the diagonal input register, and the output value register; the cell is configured to receive lowest absolute values from immediately adjacent cells and to transfer lowest values through the comparator chain to the output value register.
Reconfigurable asynchronous clock-less data co-processor with I/O terminal interface and lowest-absolute-value passing
A reconfigurable, asynchronous, clock-less data co-processor comprising a reconfigurable asynchronous and clock-less cell array core with addressable and configurable cells arranged as a multidimensional orthogonal array with input coupling and/or output coupling with each immediately adjacent cell; a plurality of data buses and control lines configured to transmit data between individual cells and within each cell; each cell including adders, numeric comparators, input registers and output registers; each cell configured during operation to receive one lowest absolute value from each immediately adjacent cell and transmit another lowest absolute value to each immediately adjacent cell; and an I/O terminal interface including a data register bus and an address bus configured to transmit row and column data between the I/O terminal interface and the cell array core, together with a plurality of control lines.
Across the independent claims, the core inventive concept is an asynchronous, clock-less, reconfigurable multidimensional orthogonal array of addressable cells in which adjacent-cell couplings and bus/control-line interfaces enable propagation of lowest absolute values using adders, numeric comparators, and input/output registers, within a co-processor having an I/O terminal interface and supporting the orthogonal array core architecture.
Stated Advantages
SWaP/power advantages are discussed in the document.
Documented Applications
Generating shortest travel paths for self-directed vehicles from geographical map parameters, including map overlay loading, start/end cell selection, computing shortest travel paths, and producing paths via readout/backtrace.
Interested in licensing this patent?