Multi-thread spreadsheet processing with dependency levels
View Patent ↗This disclosure relates to a method and system of processing chain calculations in spreadsheet applications utilizing multiple processors, each having a separate recalculation engine. A single calculation chain may be reordered into a unified chain where supporting and dependent formulas are organized into a tree hierarchy of child chains. The unified chain is further divided into dependency levels, where entries in each dependency level may be moved to a next dependency level during reordering. If an entry within a dependency level is dependent upon another entry not found within its own child chain, the unified chain is ordered such that an entry is only dependent upon an entry in a prior dependency level. Further, dependency levels allow a control thread to perform control-thread-only operations while maintaining multi-thread processing capabilities.
1. A computer-implemented method of processing formulas in a spreadsheet application, the method comprising:
ordering, by one or more processors, the formulas into a single calculation chain;
attempting to evaluate a first formula in the single calculation chain;
if the first formula is dependent upon a first supporting formula in the single calculation chain, moving the first dependent formula to a child position of the first supporting formula, wherein the moving the first dependent formula to the child position of the first supporting formula results in a first chain comprising the first dependent formula and the first supporting formula;
attempting to evaluate a second formula in the single calculation chain;
if the second formula is dependent upon a second supporting formula in the single calculation chain, moving the second dependent formula to a child position of the second supporting formula, wherein the moving the second dependent formula to the child position of the second supporting formula results in a second chain comprising the second dependent formula and the second supporting formula;
attempting to evaluate all formulas in the single calculation chain until each dependent formula has been made a child of its respective supporting formula, wherein the attempting to evaluate all formulas comprises attempting to evaluate a third formula in the single calculation chain;
if the third formula is dependent upon a third supporting formula:
moving the third formula to a child position of the third supporting formula;
determining if the third formula is also dependent upon a fourth supporting formula, wherein the fourth supporting formula is uncalculated;
if the third formula is also dependent upon a fourth uncalculated supporting formula, moving the third formula to a second dependency level, wherein a first dependency level comprises the first chain and the second chain, and wherein the first dependency level is separate from the second dependency level;
processing, by a first processor, the first chain within the first dependency level, wherein the first processor comprises a first recalculation engine; and
processing, by a second processor, the second chain within the first dependency level, wherein the second processor comprises a second recalculation engine.
2. The computer-implemented method as defined in claim 1 , wherein a fifth supporting formula has a fifth dependent formula and a sixth dependent formula and the fifth and sixth dependent formulas are moved to the second dependency level.
3. The computer-implemented method as defined in claim 1 , wherein the third supporting formula is itself the child of the second supporting formula, and wherein the fourth supporting formula is itself the child of the first supporting formula.
4. A computer-implemented method of using multiple processors to calculate formulas in a spreadsheet program, comprising:
determining the number of processors;
allocating a recalculation engine to each processor;
maintaining a control thread to synchronize the processing of the recalculation engines;
ordering the formulas into a single calculation chain;
attempting to evaluate a first formula in the single calculation chain with the first recalculation engine;
if the first formula is dependent upon a first supporting formula, moving the first dependent formula and the first supporting formula to a queue for the first recalculation engine;
attempting to evaluate a second formula in the single calculation chain with the second recalculation engine;
if the second formula is dependent upon a second supporting formula, moving the second dependent formula and the second supporting formula to a queue for the second recalculation engine;
continuing to iterate down the single calculation chain until reaching the end of the chain; and
ordering, by the control thread, the queues for the first and second recalculation engines based on dependent/supporting relationships, wherein the first dependent formula is made a child of the first supporting formula and wherein the second dependent formula is made a child of the second supporting formula.
5. The computer-implemented method as defined in claim 4 , wherein the second supporting formula is itself a child of a third supporting formula.
6. The computer-implemented method as defined in claim 4 , wherein the method further comprises:
if the first formula is dependent upon a first supporting formula, marking the first dependent formula to keep track of it;
determining if the first supporting formula is dependent upon the first dependent formula;
if the first supporting formula is dependent upon the first dependent formula, marking the first supporting formula to keep track of it;
upon finishing iterating through the single calculation chain, retrieving the tracked formulas;
determining if any of the tracked formulas are dirty;
if any of the tracked formulas are dirty, moving the tracked formula and its child or children to a flat calculation chain without any child chains or dependency levels; and
calculating the flat calculation chain using a single thread.
7. The computer-implemented method as defined in claim 4 , wherein the method further comprises:
determining whether the first dependent formula is dependent upon an uncalculated second supporting formula; and
if the first dependent formula is dependent upon the first supporting formula and dependent upon the uncalculated second supporting formula, moving the first dependent formula to a separate dependency level.
8. The computer-implemented method as defined in claim 4 , wherein the method further comprises:
determining whether the first supporting formula has both a first dependent formula and a second dependent formula; and
if the first supporting formula has both a first dependent formula and a second dependent formula, moving the first and second dependent formulas to a separate dependency level.
9. The computer-implemented method as defined in claim 4 , wherein the method further comprises:
determining whether there are any formulas in the calculation chain to be performed by the control thread only; and
moving a control-thread-only formula to a separate dependency level.
10. The computer-implemented method as defined in claim 4 , wherein a control-thread-only formula is moved to a dependency level immediately following a current dependency level.
11. The computer-implemented method as defined in claim 4 , wherein the thread operations of a first recalculation engine are suspended when the thread reaches the end of a dependency level.
12. The computer-implemented method as defined in claim 4 , wherein the thread operations of a first recalculation engine are suspended when the first recalculation engine's queue is filled.
13. The computer-implemented method as defined in claim 4 , wherein a control-thread-only formula is placed in a queue for such formulas.
14. A computer storage medium having stored thereon computer executable instructions that when executed by a processor perform a method for using multiple processors to calculate formulas in a spreadsheet program, the method comprising:
determining the number of processors;
allocating a recalculation engine to each processor;
maintaining a control thread to synchronize the processing of the recalculation engines;
ordering the formulas into a single calculation chain;
attempting to evaluate a first formula in the single calculation chain with the first recalculation engine;
if the first formula is dependent upon a first supporting formula, moving the first dependent formula and the first supporting formula to a queue for the first recalculation engine;
attempting to evaluate a second formula in the single calculation chain with the second recalculation engine;
if the second formula is dependent upon a second supporting formula, moving the second dependent formula and the second supporting formula to a queue for the second recalculation engine;
continuing to iterate down the single calculation chain until reaching the end of the chain; and
ordering, by the control thread, the queues for the first and second recalculation engines based on dependent/supporting relationships, wherein the first dependent formula is made a child of the first supporting formula and wherein the second dependent formula is made a child of the second supporting formula.
15. The computer storage medium as defined in claim 14 , wherein the second supporting formula is itself a child of a third supporting formula.
16. The computer storage medium as defined in claim 14 , further comprising:
if the first formula is dependent upon a first supporting formula, marking the first dependent formula to keep track of it;
determining if the first supporting formula is dependent upon the first dependent formula;
if the first supporting formula is dependent upon the first dependent formula, marking the first supporting formula to keep track of it;
upon finishing iterating through the single calculation chain, retrieving the tracked formulas;
determining if any of the tracked formulas are dirty;
if any of the tracked formulas are dirty, moving the tracked formula and its child or children to a flat calculation chain without any child chains or dependency levels; and
calculating the flat calculation chain using a single thread.
17. The computer storage medium as defined in claim 14 , further comprising:
determining whether the first dependent formula is dependent upon an uncalculated second supporting formula; and
if the first dependent formula is dependent upon the first supporting formula and dependent upon the uncalculated second supporting formula, moving the first dependent formula to a separate dependency level.
18. The computer storage medium as defined in claim 14 , further comprising:
determining whether the first supporting formula has both a first dependent formula and a second dependent formula; and
if the first supporting formula has both a first dependent formula and a second dependent formula, moving the first and second dependent formulas to a separate dependency level.
19. The computer storage medium as defined in claim 14 , further comprising:
determining whether there are any formulas in the calculation chain to be performed by the control thread only; and
moving a control-thread-only formula to a separate dependency level.
20. The computer storage medium as defined in claim 14 , wherein a control-thread-only formula is moved to a dependency level immediately following a current dependency level.