МНОГОПОТОЧНАЯ ОБРАБОТКА ЭЛЕКТРОННЫХ ТАБЛИЦ С ИСПОЛЬЗОВАНИЕМ УРОВНЕЙ ЗАВИСИМОСТИ

1. Способ обработки формул в программе (1520, 500) электронных таблиц, содержащий этапы на которых:
упорядочивают формулы в единую последовательность (500, 626) вычислений,
пытаются оценить первую формулу в единой последовательности (500, 628) вычислений,
если первая формула является зависимой от вспомогательной формулы в единой последовательности вычислений, перемещают первую формулу в дочернее положение относительно вспомогательной формулы (604, 630, 634), и
продолжают упорядочивать все формулы в единую последовательность вычислений до тех пор, пока каждая зависимая формула не будет сделана дочерней для соответствующей своей вспомогательной формулы, и в результате не получится объединенная последовательность (602, 604, 644) с одной или более дочерних последовательностей формул.
2. Способ по п.1, дополнительно содержащий этап на котором:
делят объединенную последовательность (602, 604) на несколько уровней (618, 620) зависимости, причем каждый уровень зависимости содержит формулы (608, 610, 612, 642, 640), которые являются зависимыми только от формул из предыдущего уровня (618) зависимости или от формул внутри их собственных дочерних последовательностей (608, 610, 640, 642).
3. Способ по п.2, в котором зависимую формулу (612) перемещают на следующий уровень зависимости, если она является дочерней для первой вспомогательной формулы (610) и является зависимой от невычисленной второй вспомогательной формулы (608, 636, 642).
4. Способ по п.2, в котором вспомогательная формула имеет первую зависимую формулу и вторую зависимую формулу, и первую и вторую зависимые формулы перемещают на следующий уровень (638, 640) зависимости.
5. Компьютерный программный продукт (1508, 1520), считываемый вычислительной системой (1500), и материально воплощающий программу из инструкций, выполняемых вычислительной системой для выполнения способа по п.1.
6. Способ использования нескольких процессоров для вычисления формул в программе (200, 1000) электронных таблиц, содержащий этапы, на которых:
определяют количество процессоров (206),
выделяют механизм повторного вычисления для каждого процессора (209),
поддерживают поток управления для синхронизации обработки механизмов (1004) повторного вычисления,
упорядочивают формулы в единую последовательность (700, 626) вычислений,
пытаются оценить первую формулу в единой последовательности вычислений первым механизмом (708, 628, 1120) повторного вычисления,
если первая формула является зависимой от первой вспомогательной формулы, перемещают первую зависимую формулу и первую вспомогательную формулу в очередь для первого механизма (706, 636, 1122) повторного вычисления,
пытаются оценить вторую формулу в единой последовательности вычислений вторым механизмом (708, 1124, 1138) повторного вычисления,
если вторая формула является зависимой от второй вспомогательной формулы, перемещают вторую зависимую формулу и вторую вспомогательную формулу в очередь для второго механизма (710, 1138, 1140) повторного вычисления, и
продолжают выполнение итерации вниз по единой последовательности вычислений до достижения конца последовательности (708, 706, 710, 1142, 644).
7. Способ по п.6, дополнительно содержит этапы, на которых опустошают очереди каждого механизма повторного вычисления для переупорядочения (1122, 1140), причем первую зависимую формулу делают дочерней для первой вспомогательной формулы, и при этом вторую зависимую формулу делают дочерней для второй вспомогательной формулы (802, 804, 630, 634).
8. Способ по п.7, в котором вторая вспомогательная формула сама является дочерней для третьей вспомогательной формулы (804).
9. Способ по п.6, причем способ дополнительно содержит этапы, на которых:
если первая формула является зависимой от первой вспомогательной формулы, то маркируют первую зависимую формулу для ее отслеживания (1420),
определяют, является ли первая вспомогательная формула зависимой от первой зависимой формулы (1414, 1418),
если первая вспомогательная формула является зависимой от первой зависимой формулы, маркируют первую вспомогательную формулу для ее отслеживания (1420),
извлекают отслеженные формулы (1422, 1424) после окончания итераций по единой последовательности вычислений,
определяют, является ли какая-либо из отслеживаемых формул “грязной” (1426),
если отслеживаемые формулы являются “грязными”, то перемещают отслеживаемые формулы и их дочерние формулы или в одноуровневую последовательность вычислений без каких-либо дочерних последовательностей или уровней зависимости (1428), и
вычисляют одноуровневую последовательность вычислений с использованием одного потока (1432).
10. Способ по п.6, причем способ дополнительно содержит этапы, на которых:
определяют, является ли первая зависимая формула зависимой от невычисленной второй вспомогательной формулы (802, 804, 612, 636); и
если первая зависимая формула является зависимой от первой вспомогательной формулы и является зависимой от невычисленной второй вспомогательной формулы, то перемещают первую зависимую формулу на отдельный уровень (610, 612, 618, 620, 636, 642) зависимости.
11. Способ по п.6, причем способ дополнительно содержит этапы, на которых:
определяют, имеет ли первая вспомогательная формула и первую зависимую формулу и вторую зависимую формулу (1132, 638), и
если первая вспомогательная формула имеет и первую зависимую формулу и вторую зависимую формулу, перемещают первую и вторую зависимые формулы на отдельный уровень (612, 620, 638, 640) зависимости.
12. Способ по п.6, причем способ дополнительно содержит этапы, на которых:
определяют, существуют ли в последовательности вычислений формулы, которые должны быть выполнены только потоком управления (1206), и
перемещают формулы только потока управления на отдельный уровень зависимости (1212).
13. Способ по п.6, в котором формулу только потока управления перемещают на уровень зависимости, непосредственно следующий за текущим уровнем зависимости (1130).
14. Способ по п.6, в котором операции потока первого механизма повторного вычисления приостанавливают при достижении потоком конца уровня зависимости (1132, 1134).
15. Способ по п.6, в котором операции потока первого механизма повторного вычисления приостанавливают при заполнении очереди первого механизма повторного вычисления (1132, 1134).
16. Способ по п.6, в котором формулу только потока управления помещают в очередь для таких формул. (1132, 1130).
17. Компьютерный программный продукт (1508, 1520), считываемый вычислительной системой и материально воплощающий программу из инструкций, выполняемых вычислительной системой (1500), для выполнения способа по п.6.
18. Способ переупорядочения последовательности вычислений в приложении электронных таблиц посредством использования уровней зависимости, содержащий этапы, на которых:
создают первый уровень зависимости, содержащий первую дочернюю последовательность и вторую дочернюю последовательность (618, 608, 610, 642, 640),
пытаются оценить каждую формулу в первой дочерней последовательности (608, 628),
пытаются попытки оценить каждую формулу во второй дочерней последовательности (608, 628),
если формула не может быть оценена, определяют, является ли формула зависимой от первой вспомогательной формулы в ее собственной дочерней последовательности и зависимой от второй вспомогательной формулы в другой дочерней последовательности в рамках того же уровня зависимости (612, 620, 630, 636),
определяют, является ли вторая вспомогательная формула невычисленной (612, 620, 636),
если вторая вспомогательная формула является невычисленной, перемещают зависимую формулу на следующий уровень (612, 642) зависимости, и
если вторая вспомогательная формула является вычисленной, оценивают зависимую формулу на текущем уровне (604, 632) зависимости.
19. Способ по п.18, причем способ дополнительно содержит этапы, на которых:
определяют, имеет ли первая вспомогательная формула, от которой уже зависит первая зависимая формула, вторую зависимую формулу в виде дочерней (630, 638), и
если первая вспомогательная формула уже имеет дочернюю, то перемещают первую и вторую зависимые формулы на следующий уровень (638, 640) зависимости.
20. Способ по п.18, причем способ дополнительно содержит этапы, на которых:
определяют, существуют ли формулы только потока управления (1206), и
если существуют формулы только потока управления, то перемещают эти элементы на следующий уровень зависимости (1206, 1212).