Short-circuit evaluation of Boolean expression by rolling up sub-expression result in registers storing default value

• US 8,307,197 B2
• Filed: 02/02/2009
• Issued: 11/06/2012
• Est. Priority Date: 02/14/2001
• Status: Expired due to Fees

• 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
• Primary Examiner(s): KIM, KENNETH S
• Application Number:
  US12/364,047
• Publication Number:
  US 20090138679A1
• Time in Patent Office: 1,373 Days
• Field of Search: None
• US Class Current: 712/223
• 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 configured to perform a short-circuit evaluation of a Normal Form Boolean expression/operation, wherein performing a short-circuit evaluation comprises halting the evaluation of at least a portion of the Normal Form Boolean expression/operation if the outcome of the portion becomes known based on an outcome of an evaluation of a prior portion of the Normal Form Boolean expression/operation by the Boolean logic unit;

a plurality of input/output interfaces in communication with the Boolean logic unit, wherein the plurality of input/output interfaces are configured 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 interfaces, wherein the plurality of registers comprise;

a first register for storing the outcome of the most recently evaluated conjunct or disjunct; and

a second register for rolling up the results of the conjuncts or disjuncts;

wherein the second register is initially set to a default value;

wherein, the Boolean Logic unit is further configured to perform the following logic;

if the expression is a conjunct and the evaluation of the conjunct expression stored in the first register is zero or its logical equivalent, then the value of the second register is set to a value other than its default value;

if the expression is a disjunct and the evaluation of the disjunct expression stored in the first register is one or its logical equivalent, then the value of the second register is set to a value other than its default value;

if the value of the second register is set to a value other than its default value, then the processor halts evaluation of the remainder of the expression/operation and provides the result of the expression/operation via one of the input/output interfaces.

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 by performing a short-circuit evaluation of the 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 interfaces, the method comprising:

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

(b) storing the outcome of the most recently evaluated conjunct or disjunct in a first register;

(c) initially setting a second register to a default value;

(d) rolling up the results of a conjunct or disjunct in the second register;

(e) setting the value of the second register to a value other than its default value if the expression is a conjunct and the evaluation of the conjunct expression stored in the first register is zero or its logical equivalent;

(f) setting the value of the second register to a value other than its default value if the expression is a disjunct and the evaluation of the disjunct expression stored in the first register is one or its logical equivalent; and

(g) halting the evaluation of the remainder of the expression/operation and providing the result of the expression/operation via an input/output interface if the value of the second register is set to a value other than its default value.

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 receiving a Normal Form Boolean expression comprises receiving a plurality of conjuncts or a plurality of disjuncts, and wherein evaluating the plurality of conjuncts or disjuncts 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 short-circuiting includes:

if a conjunct in a first separate Boolean processor results in a false evaluation, providing a signal, from a first separate Boolean processor to one or more 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 short-circuiting includes:

if a disjunct in a first separate Boolean processor results in a true evaluation, providing a signal, from the a first separate Boolean processor to one or more 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 for converting a plurality of conditional tests into a result of a Boolean expression, said method comprising:

receiving the plurality of conditional tests at a processor;

based upon the received plurality of conditional tests, generating an operation, in computer-readable format, representative of the 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 interfaces;

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

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

storing the outcome of the most recently evaluated conjunct or disjunct in a first register;

initially setting a second register to a default value;

rolling up the results of a conjunct or disjunct in the second register;

setting the value of the second register to a value other than its default value if the expression is a conjunct and the evaluation of the conjunct expression stored in the first register is zero or its logical equivalent;

setting the value of the second register to a value other than its default value if the expression is a disjunct and the evaluation of the disjunct expression stored in the first register is one or its logical equivalent; and

halting the evaluation of the remainder of the expression/operation and providing the result of the expression/operation via an input/output interface if the value of the second register is set to a value other than its default value.

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.