Enhanced Boolean Processor

• US 20090138679A1
• Filed: 02/02/2009
• Published: 05/28/2009
• Est. Priority Date: 02/14/2001
• Status: Active Grant

• Current Assignee: University of North Carolina At Charlotte (University of North Carolina System)
• Original Assignee: University of North Carolina At Charlotte (University of North Carolina System)
• Inventors: Koch, Kenneth Elmon III
• Granted Patent: US 8,307,197 B2
• Time in Patent Office: Days
• US Class Current: 712/205
• CPC Class Codes: G06F 9/264 Microinstruction selection based on results of processing
• CPC Class Codes: G06F 9/30029 Logical and Boolean instructions, e.g. XOR, NOT
• CPC Class Codes: G06F 9/3879 for non-native instruction execution, e.g. executing a command; for Java instruction set

Abstract

A processor including a Boolean logic unit, wherein the Boolean logic unit is operated for performing the short-circuit evaluation of a Normal Form Boolean expression/operation, a plurality of input/output interfaces in communication with the Boolean logic unit, wherein the plurality of input/output interfaces are operated for receiving a plurality of compiled Boolean expressions/operations and transmitting a plurality of compiled results, and a plurality of registers coupled to the plurality of input/output interface circuits, wherein the plurality of multi-bit registers include an instruction register, a first address register and a second address register.

Claims

1. A processor, comprising:

a Boolean logic unit, wherein the Boolean logic unit is operated for performing the short-circuit evaluation of a Normal Form Boolean expression/operation;

a plurality of input/output interfaces in communication with the Boolean logic unit, wherein the plurality of input/output interfaces are operated for receiving a plurality of compiled Boolean expressions/operations and transmitting a plurality of compiled results; and

a plurality of registers coupled to the plurality of input/output interface circuits, wherein the plurality of multi-bit registers comprise an instruction register, a first address register and a second address register.

2. The processor of claim 1, further comprising a p-bit OR register, wherein the p-bit OR register is operable for rolling up the results of disjuncts.

3. The processor of claim 1, further comprising a q-bit AND register, wherein the q-bit AND register is operable for storing the results of the evaluation of one or more terms within disjuncts.

4. The processor of claim 3, further comprising an r-bit AND disjunct register, wherein the r-bit AND disjunct register indicates that the evaluation of a disjunct comprising an AND clause has begun.

5. The processor of claim 4, wherein the r-bit AND disjunct register initializes to a value of ‘

zero’

, or its logical equivalent, and remains in that state until an AND expression/operation sets its value to ‘

one’

or its logical equivalent and wherein the value of the r-bit AND disjunct register remains at ‘

one’

, or its logical equivalent, until reset by a Boolean OR operational code, an end of operation operational code, or a start of operation operational code.

6. The processor of claim 4, wherein a predetermined disjunct evaluates to false if the q-bit AND register is set to ‘

zero’

, or its logical equivalent, and the r-bit AND disjunct register is set to ‘

one’

, or its logical equivalent, and the processor short-circuits to the start of the next disjunct.

7. The processor of claim 1 further comprising a p-bit AND/OR register, wherein the p-bit AND/OR register is operable for rolling up the results of conjuncts and/or disjuncts.

8. The processor of claim 1, further comprising a q-bit AND/OR register, wherein the q-bit AND/OR register is operable for storing the results of the evaluation of one or more terms within conjuncts and disjuncts.

9. The processor of claim 1, further comprising:

one or more memory devices in communication with the processor, wherein the one or more memory devices are operable for storing the states of a plurality of devices that the processor monitors and controls, wherein the states are each stored in a particular memory location, and wherein the random-access memory includes at least one bit associated with each memory location, and wherein the at least one bit is operable for indicating whether or not the device state stored in the respective memory location is in the process of being modified; and

a circuit in communication with the one or more memory devices operated for;

setting the at least one bit of each memory location at the beginning of the process of modifying the device state stored in the respective memory location and for clearing the at least one bit of the respective memory location at the end of the process of modifying the device state stored therein;

or

preventing the processor from reading a device state from a memory location when the at least one bit associated with the memory location indicates that the device state stored in the memory location is in the process of being modified.

10. The processor of claim 1, further comprising a control store, wherein the control store is operable for holding a compiled micro-program, a program counter, wherein the program counter is operable for fetching an instruction from the control store, and a device, wherein the device is operable for configuring the program counter for performing the short-circuit evaluation of a Normal Form Boolean expression/operation.

11. A method for processing a Boolean expression using a processor comprising a Boolean logic unit, wherein the Boolean logic unit is in communication with a plurality of input/output interfaces, and a plurality of registers coupled to the plurality of input/output interface circuits, the method comprising:

(a) receiving a Normal Form Boolean expression, wherein the Normal Form Boolean expression comprises a conjunct or a disjunct;

(b) evaluating the conjunct or disjunct;

(c) selectively short-circuiting a portion of the Normal Form Boolean expression; and

(d) outputting a result of the Normal Form Boolean expression.

12. The method of claim 11, wherein receiving a Normal Form Boolean expression comprises receiving a Disjunctive Normal Form Boolean expression, wherein the Normal Form Boolean expression comprises a disjunct, and wherein evaluating includes evaluating the disjunct.

13. The method of claim 11, wherein starting an operation includes starting an operation related to a Normal Form Boolean expression, wherein the Boolean expression comprises a plurality of conjuncts or a plurality of disjuncts, and wherein evaluating the conjunct or disjunct includes:

separating the Boolean expression into separate conjuncts or disjuncts; and

distributing each separate conjunct or disjunct to a separate Boolean processor for evaluation.

14. The method of claim 13, wherein if the Boolean expression is a Conjunctive Normal Form Boolean expression, then selectively short-circuiting includes:

if a conjunct in a first separate Boolean processor results in a false evaluation, providing a signal, from the first separate Boolean processor to the other separate Boolean processors, that the entire expression is false.

15. The method of claim 13, wherein if the Boolean expression is a Disjunctive Normal Form Boolean expression, then selectively short-circuiting includes:

if a disjunct in a first separate Boolean processor results in a true evaluation, providing a signal, from the first separate Boolean processor to the other separate Boolean processors, that the entire expression is true.

16. The method of claim 11, wherein if the Boolean logic circuit is operated for performing the short-circuit evaluation of Conjunctive Normal Form (“

CNF”

) Boolean expressions/operations, then the first address register is activated as a next operation address register and the second address register is activated as an end of OR address register, the output of the first address register is an address of a CNF expression immediately following the CNF expression being evaluated, and the output of the second address register is the address of the conjunct immediately following the conjunct being evaluated, wherein the output occurs in the event that the Boolean logic unit delivers an indication that the final evaluation of the CNF expression has been determined (false) to the first address register or an indication that the final evaluation of the current conjunct has been determined (true) to the second address register;

wherein if the Boolean logic circuit is operated for performing the short-circuit evaluation of Disjunctive Normal Form (“

DNF”

) Boolean expressions/operations, then the first address register is activated as an end of operation address register and the second address register is activated as an end of AND address register, the output of the first address register is the address of the DNF expression immediately following the DNF expression being evaluated and the output of the second address register is the address of the disjunct immediately following the disjunct being evaluated, wherein the output occurs in the event that the Boolean logic unit delivers an indication that the final evaluation of the DNF expression has been determined (true) to the first address register or an indication that the final evaluation of the current disjunct has been determined (false) to the second address register; and

wherein if the Boolean logic circuit is operated for performing the short-circuit evaluation of both Conjunctive and Disjunctive Normal Form Boolean expressions/operations, then the first address register is activated as a next operation/end of operation address register and the second address register is activated as an end of OR/AND address register, the output of the first address register is the address of the CNF/DNF expression immediately following the current CNF/DNF expression and the output of the second address register is the address of the conjunct/disjunct immediately following the current conjunct/disjunct, wherein the output occurs in the event that the Boolean logic unit delivers an indication that the final evaluation of the CNF/DNF expression has been determined to the first address register or an indication that the final evaluation of the current conjunct/disjunct has been determined to the second address register.

17. A compiling method, comprising:

receiving a plurality of conditional tests at a processor;

based upon the received plurality of conditional tests, generating an operation, in computer-readable format, representative of a Boolean expression in Conjunctive Normal Form or Disjunctive Normal Form;

storing the operation in a Boolean processor comprising a Boolean logic unit, wherein the Boolean logic unit is in communication with a plurality of input/output interfaces, and a plurality of registers coupled to the plurality of input/output interface circuits;

evaluating the Boolean expression by processing the operation and selectively short-circuiting a portion of the Boolean expression on the Boolean processor; and

outputting a result of the Boolean expression.

18. The method of claim 17, wherein the generated operation includes a plurality of portions, wherein at least a first of the plurality of portions is more likely to create a short-circuit condition than at least a second of the plurality of portions, and wherein generating an operation includes ordering the plurality of portions within the operation such that the first of the plurality of portions is likely to be processed before the second of the plurality of portions.

19. The method of claim 18, further comprising:

determining the relative likelihood of at least the first and second of the plurality of portions to create a short-circuit condition.

20. The method of claim 19, wherein determining includes determining a probability of the first of the plurality of portions to create a short-circuit condition and a probability of the second of the plurality of portions to create a short-circuit condition, the method further comprising:

storing, in a memory, the probability of the first of the plurality of portions to create a short-circuit condition and the probability of the second of the plurality of portions to create a short-circuit condition.