Tropical algebra is an emerging field of mathematics concerned with graph theory, control theory, and certain optimization problems, especially in discrete event systems. We developed a novel computer circuit called a tropical state machine that uses signal timing and the physics of nanodevices to implement tropical algebra calculations orders of magnitude faster and more energy efficiently than on a standard central processing unit. Our circuit is modular and can be expanded in obvious ways to include additional functionality, but contains key elements including temporal memories and tropical vector-matrix-multipliers that form the essential basic ingredients of any tropical state machine.
The invention is a circuit/computer architecture that supports the rapid, energy efficient evaluation of tropical algebra primitives. These operations that choose the minimum or maximum elements among those in an array; operations that add together two values; operations that choose execute tropical dot products and matrix-vector products, which constitute efficiently composed sum and minimum operations; operations that filter vectors to become so-called “one-hot” vectors labeling their minimal element; operations that implement tropical ramp functions, so-called “inhibit” operations; and other operations composed of these primitives operations, as needed for a particular application. A necessary support element for these operations which is novel to the tropical state machine is the concept of a temporal wavefront memory.