Method for operating a parallel processing system and related apparatus

Claim 3

The method of claim 1 further including the steps of: determining, by each said processor, ready ones of said production rules for which that processor has formed a first set or a next set satisfying all of said conditions of the rules; choosing, by each said processor, one of the ready production rules; communicating the chosen production rules from said processors to a priority determination element; and selecting, by said priority determination element, one of said chosen production rules according to a predetermined priority scheme, to obtain a selected production rule.

Claim 4

The method of claim 2 wherein said selecting step is performed by a one of said processors.

Claim 5

The method of claim 3 wherein said priority determination element is said one processor.

Claim 6

The method of claim 2 wherein the step of performing the specified operations includes the step of performing the operations specified by the selected production rule.

Claim 7

The method of claim 5 wherein each of said working memory elements includes a time tag; wherein said communicating step includes the step of communicating information about the working memory elements which satisfy the chosen production rules; and wherein said selecting step includes the step of using a priority scheme based on the time tags in the working memory elements satisfying the chosen production rules.

Claim 8

The method of claim 6 wherein said choosing step includes the step of comparing to each other the time tags of the working memory elements satisfying the ready production rules.

Claim 9

The method of claim 7 wherein said subdividing step includes the step of assigning subsets to processors according to the time tags in at least one working memory element in the subsets.

Claim 10

The method of claim 1 wherein said operations performing step is performed by a master processor.

Claim 11

The method of claim 9 wherein said master processor is one of said plurality of processors.

Claim 12

The method of claim 1 wherein the sequence of steps of claim 1 are repeated.

Claim 13

The method of claim 1 wherein said processes each have a local memory, and wherein said method includes the step of storing said working memory elements and said production rules into said local memories.

Claim 14

The method of claim 1 wherein said processors each have a local memory and are coupled to a shared memory, and wherein said method further includes the steps of: storing certain of said working memory elements and said production rules into said local memories; and storing the other of said working memory elements and said production rules into said shared memory.

Claim 15

The method of claim 1 wherein said step of subdividing occurs after the step of forming said first sets and before the step of forming said sequences of next sets.

Claim 16

The method of claim 1 wherein said production rules each indicate a level of subdivision corresponding to one of the series of conditions for that rule, and wherein for each rule said step of subdividing for each rule occurs at the level indicated for that production rule.

Claim 17

The method of claim 1 wherein certain of said conditions include condition tests, and wherein the forming steps each include the step of ensuring that the ones of said working memory elements satisfying the conditions including condition tests also meet said condition tests.

Claim 18

The method of claim 1 wherein said step of subdividing said sets includes the step of classifying said sets into the same number of classes as the number of processors according to a characteristic of the next sets such that each of said classes corresponds to one of said processors.

Claim 19

The method of claim 17 wherein the step of classifying said sets is performed in accordance with a characteristic of said working memory elements of the sets being classified.

Claim 20

A parallel processing system having a plurality of processors, said processors having access to working memory elements to be examined and said processors implementing production rules specifying operations to be performed when a series of conditions are satisfied by specified ones of the working memory elements, the system comprising: a plurality of identifying means for identifying, by each said processor substantially simultaneously, groups of said working memory elements, each of said groups corresponding to a unique one of the conditions of each of said production rules such that all of the elements in each group satisfy the corresponding condition; a plurality of first forming means for forming, by each said processor substantially simultaneously and from said groups of working memory elements, first sets of pairs of said working memory elements, each of said first sets corresponding to a unique one of said production rules, the elements in each of the pairs in said first sets respectively satisfying first and second conditions of the corresponding production rule; a plurality of second forming means for forming, by each said processor substantially simultaneously and from said groups of working memory elements, sequences of next sets of said working elements, each said sequence being associated with at least one of said production rules such that each said next set in each said sequence corresponds to a next one of the series of conditions for the associated production rules, each of next said set in each of said sequences containing working memory elements contained in a prior set in that sequence as well as working memory elements from said groups which satisfy the corresponding condition in the associated production rule; a plurality of subdividing means for subdividing, by each said processor substantially simultaneously, a selected one of said first sets or said next sets into N unique, nonoverlapping subsets where N is no greater than the number of processors, each of said subsets corresponding to one of said processors, each said processor only forming the next sets in each sequence succeeding said corresponding subset; and performing means for performing all of the operations specified by one of the production rules for which all conditions have been satisfied.

Claim 21

A parallel processing system having a plurality of processors, said processors having access to working memory elements to be examined and said processors implementing production rules specifying operations to be performed when a series of conditions are satisfied by specified ones of the working memory elements, the system comprising: a plurality of identifying means for identifying, by each said processor substantially simultaneously, groups of said working memory elements, each of said groups corresponding to a unique one of the conditions of each of said production rules such that all of the elements in each group satisfy the corresponding condition; a plurality of first forming means for forming, by each said processor substantially simultaneously and from said groups of working memory elements, first sets of pairs of said working memory elements, each of said first sets corresponding to a unique one of said production rules, the elements in each of the pairs in said first sets respectively satisfying first and second conditions of the corresponding production rule; a plurality of second forming means for forming, by each said processor substantially simultaneously and from said groups of working memory elements, sequences of next sets of said working elements, each said sequence being associated with at least one of said production rules such that each said next set in each said sequence corresponds to a next one of the series of conditions for the associated production rules, each of next said set in each of said sequences containing working memory elements contained in a prior set in that sequence as well as working memory elements from said groups which satisfy the corresponding condition in the associated production rule; a plurality of subdividing means for subdividing, by each said processor substantially simultaneously, a selected one of said first sets or said next sets into N unique, nonoverlapping subsets where N is no greater than the number of processors, each of said subsets corresponding to one of said processors, each said processor only forming the next sets in each sequence succeeding said corresponding subset; and performing means for performing all of the operations specified by one of the production rules for which all conditions have been satisfied.

Claim 22

The system of claim 19 further including: a plurality of determining means for determining, by each said processor, ready ones of said production rules for which that processor has formed a first set or a next set satisfying all of said conditions of the rules; a plurality of choosing means for choosing, by each said processor, one of the ready production rules; communication means for communicating the chosen production rules from said processors; and priority determination means for selecting one of said chosen production rules from said communication means according to a predetermined priority scheme, to obtain a selected production rule.

Claim 23

The system of claim 20 wherein said priority determination means is one of said processors.

Claim 24

The system of claim 20 wherein the performing means includes means for performing the operations specified by the selected production rule.

Claim 25

The system of claim 22 wherein each of said working memory elements includes a time tag; wherein said communication means includes means for communicating information about the working memory elements which satisfy the chosen production rules; and wherein the priority scheme of said priority determination means is based on the time tags in the working memory elements satisfying the chosen production rules.

Claim 26

The system of claim 23 wherein said choosing means each include means for comparing to each other the time tags of the working memory elements satisfying the production rules.

Claim 27

The system of claim 24 wherein said subdividing means each include means for assigning subsets to processors according to the time tags in at least one working memory element in the subsets.

Claim 28

The system of claim 19 wherein said performing means is located in a master processor.

Claim 29

The system of claim 26 wherein said master processor is one of said plurality of processors.

Claim 30

The system of claim 19 wherein said processors each have a local memory, and wherein said system includes storing means for storing said working memory elements and said production rules into said local memories.

Claim 31

The system of claim 19 wherein said processors each have a local memory and are coupled to a shared memory, and wherein said system further includes: first storing means for storing certain of said working memory elements and said production rules into said local memories; and second storing means for storing the other of said working memory elements and said production rules into said shared memory.

Claim 32

The system of claim 19 wherein said production rules each indicate a level of subdivision corresponding to one of the series of conditions for that rule, and wherein for each rule said subdividing means subdivide the sets for each rule at the level indicated for that production rule.

Claim 33

The system of claim 19 wherein certain of said conditions include condition tests, and wherein the first and second forming means each include an element for ensuring that the ones of said working memory elements satisfying the conditions including condition tests also meet said condition tests.

Claim 34

The system of claim 19 wherein the subdividing means each include means for classifying said sets into the same number of classes as the number of processors according to a characteristic of the next sets such that each of said classes corresponds to one of said processors.

Claim 35

The system of claim 32 wherein said classifying means classify said sets in accordance with a characteristic of said working memory elements of the sets being classified.

Claim 36

A computer processing means for operating a processor in a parallel processing system having a plurality of processors, said processors having access to working memory elements to be examined and said processors implementing production rules specifying operations to be performed when a series of conditions are satisfied by specified ones of the working memory elements, the processing means comprising: identifying means for identifying, substantially simultaneously with the other said processors, groups of said working memory elements, each of said groups corresponding to a unique one of the conditions of each of said production rules such that all of the elements in each group satisfy the corresponding condition; first forming means for forming, substantially simultaneously with the other said processors and from said groups of working memory elements, first sets of pairs of said working memory elements, each of said sets corresponding to a unique one of said production rules, the elements in each of the pairs in said first sets respectively satisfying first and second conditions of the corresponding production rule; second forming means for forming, substantially simultaneously with the other said processors and from said groups of working memory elements, sequences of next sets of said working elements, each said sequence being associated with at least one of said production rules such that each said next set in each said sequence corresponds to a next one of the series of conditions for the associated production rules, each of said next set in each of said sequences containing working memory elements contained in a prior set in that sequence as well as working memory elements from said groups which satisfy the corresponding condition in the associated production rule; subdividing means for subdividing, substantially simultaneously with the other of said processors, a selected one of said first sets or said next sets into a unique subset, said processor only forming the next sets in each sequence succeeding said subset; determining means for determining ready ones of said production rules for which said processor has formed a first set or a next set satisfying all of said conditions of the rules; choosing means for choosing one of the ready production rules; and communication means for communicating the chosen production rules to priority determination means for selecting one of said chosen production rules.

Claim 37

A computer processing means for operating a processor in a parallel processing system having a plurality of processors, said processors having access to working memory elements to be examined and said processors implementing production rules specifying operations to be performed when a series of conditions are satisfied by specified ones of the working memory elements, the processing means comprising: identifying means for identifying, substantially simultaneously with the other said processors, groups of said working memory elements, each of said groups corresponding to a unique one of the conditions of each of said production rules such that all of the elements in each group satisfy the corresponding condition; first forming means for forming, substantially simultaneously with the other said processors and from said groups of working memory elements, first sets of pairs of said working memory elements, each of said sets corresponding to a unique one of said production rules, the elements in each of the pairs in said first sets respectively satisfying first and second conditions of the corresponding production rule; second forming means for forming, substantially simultaneously with the other said processors and from said groups of working memory elements, sequences of next sets of said working elements, each said sequence being associated with at least one of said production rules such that each said next set in each said sequence corresponds to a next one of the series of conditions for the associated production rules, each of said next set in each of said sequences containing working memory elements contained in a prior set in that sequence as well as working memory elements from said groups which satisfy the corresponding condition in the associated production rule; subdividing means for subdividing, substantially simultaneously with the other of said processors, a selected one of said first sets or said next sets into a unique subset, said processor only forming the next sets in each sequence succeeding said subset; determining means for determining ready ones of said production rules for which said processor has formed a first set or a next set satisfying all of said conditions of the rules; choosing means for choosing one of the ready production rules; and communication means for communicating the chosen production rules to priority determination means for selecting one of said chosen production rules.

Claim 38

The computer processing means of claim 34 wherein each of said working memory elements includes a time tag; and wherein said communication means includes means for communicating information about the working memory elements which satisfy the chosen production rules.

Claim 39

The computer processing means of claim 35 wherein said choosing means includes means for comparing to each other the time tags of the working memory elements satisfying the production rules.

Claim 40

The computer processing means of claim 36 wherein said subdividing means includes means for assigning a subset to the processor according to the time tags in at least one working memory element in the subset.

Claim 41

The computer processing means of claim 34 wherein said production rules each indicate a level of subdivision corresponding to one of the series of conditions for that rule, and wherein for each rule said subdividing means subdivides the sets for each rule at the level indicated for that production rule.

Claim 42

The computer processing means of claim 34 wherein certain of said conditions include condition tests, and wherein the first and second forming means each include means for ensuring that the ones of said working memory elements satisfying the conditions including condition tests also meet said condition tests.

Claim 43

The computer processing means of claim 34 wherein the subdividing means includes means for classifying said sets into classes according to a characteristic of said working memory elements of the sets being classified.