Многопоточная обработка электронных таблиц с использованием уровней зависимости

Многопоточная обработка электронных таблиц с использованием уровней зависимости

Иллюстрации

Показать все

Реферат

УРОВЕНЬ ТЕХНИКИ

Для анализа данных стало распространенным использование приложений электронных таблиц. Дополнительно, так как деловая активность все более зависит от указанных приложений для сложного вычисления данных, возникла потребность в более быстрой и более эффективной обработке указанных приложений. Примером такого приложения электронных таблиц является Microsoft Excel^TM. В приложениях электронных таблиц стало обычным наличие в одной ячейке формулы, определенной как "зависимая" формула, которая зависит от содержимого или формулы в другой ячейке, определенной как "вспомогательная" формула. При изменении содержимого ячейки может быть запущена операция повторного вычисления ("recalc"), в которой используют программный поток для повторного прохода по формулам и повторного вычисления любых формул, для которых требуется повторное вычисление на основе указанных изменений. Для операций вычисления может быть уменьшено в отношении быстродействия время обработки при отсутствии совместной приостановки в течение существенного периода времени, когда программный поток повторного вычисления сталкивается с формулой, зависимой от вспомогательной формулы, которая еще должна быть вычислена. Даже в случаях, где в таких приложениях применяют несколько процессоров или несколько программных потоков, скорость выполнения вычислений и повторных вычислений не может быть повышена там, где, по меньшей мере, один из процессоров не обеспечен возможностью завершения вычисления или повторного вычисления, ожидая вычисления вспомогательной формулы. Проблема усугубляется при увеличении количества зависимых формул в приложении электронных таблиц.

Хотя в описании Уровня Техники были упомянуты определенные проблемы, это раскрытие ни в коей мере не ограничено решением указанных определенных проблем.

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

Варианты осуществления настоящего изобретения, в основном, относятся к обработке вычислений и повторных вычислений электронных таблиц с использованием нескольких процессоров или нескольких параллельных потоков, когда доступны более одного процессора или механизма обработки. Дополнительные варианты осуществления относятся к использованию структуры дерева и уровней зависимости при переупорядочении последовательности элементов для выполнения многопоточной обработки операции повторного вычисления. Еще дополнительно, некоторые варианты осуществления относятся к синхронизации многопоточной обработки операций повторного вычисления.

Как здесь описано, аспект определенного варианта осуществления относится к переупорядочению последовательности вычисления элементов, или "ENT", так чтобы была создана объединенная последовательность повторного вычисления, состоящая из дочерних последовательностей (то есть зависимых формул и вспомогательных формул, организованных в иерархии дерева) и элементов ENT, которые не содержат ни зависимой, ни вспомогательной формулы. "ENT" относится к формуле, содержащейся внутри ячейки электронной таблицы. В другом варианте осуществления объединенную последовательность разделяют на отдельные уровни зависимости, при этом каждый уровень зависимости содержит элементы ENT, которые зависят только от элементов ENT на предыдущих уровнях зависимости, кроме тех, которые являются зависимыми от вспомогательной формулы в дочерней последовательности внутри того уровня зависимости. Конфигурация в таком варианте осуществления обеспечивает возможность продолжения обработки несколькими потоками элементов ENT по уровню зависимости без необходимости ожидания вычисления невычисленных вспомогательных ENT. При достижении следующего уровня зависимости обработку находящихся на нем элементов ENT и дочерних последовательностей (если существуют) эффективно выполняют на основе уже завершенных вычислений на предыдущих уровнях зависимости.

Дополнительные варианты осуществления относятся к использованию нескольких асинхронных программных потоков там, где система состоит более чем из одного процессора или механизма обработки для оценки формул в этой объединенной последовательности повторного вычисления. В варианте осуществления для управления синхронизацией этой многопоточной обработки может быть использован поток управления.

Эта сущность изобретения обеспечена для представления в упрощенном виде выбора концепций, которые дополнительно описаны ниже в Подробном описании изобретения. Эта Сущность изобретения не предназначена ни для определения ключевых или основных признаков предмета обсуждения, ни для использования в какой-либо степени для ограничения контекста заявленного предмета обсуждения.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

Фиг.1 иллюстрирует логическое представление примерных модулей функциональных компонентов, включая количество "N" механизмов повторного вычисления ("механизмов recalc"), используемых в приложении электронных таблиц согласно варианту осуществления настоящего изобретения.

Фиг.2 изображает основные операции, выполняемые системой, изображенной на фиг.1, для загрузки приложения электронных таблиц и определения количества процессоров для использования в них согласно варианту осуществления настоящего изобретения.

Фиг.3 иллюстрирует основные операции, выполняемые системой, изображенной на фиг.1, для выполнения механизмами повторного вычисления, изображенными на фиг.1, операции повторного вычисления согласно варианту осуществления настоящего изобретения.

Фиг.4 изображает примерную электронную таблицу 3x3, изображая элементы ячейки со значениями и/или несколькими формулами, в приложении электронных таблиц, с использованием модулей функциональных компонентов, иллюстрированных фиг.1 согласно варианту осуществления настоящего изобретения.

Фиг.5 иллюстрирует ячейки электронной таблицы, изображенной на фиг.4, при первоначальной загрузке в единую последовательность вычислений согласно варианту осуществления настоящего изобретения.

Фиг.6А изображает ячейки, изображенные на фиг.4 и фиг.5, переупорядоченные в объединенную последовательность повторного вычисления дочерних последовательностей.

Фиг.6B изображает дочерние последовательности фиг.6A, загруженные в два механизма повторного вычисления и разделенные на уровни зависимости, при этом одна ячейка была перемещена на второй уровень зависимости согласно варианту осуществления настоящего изобретения.

Фиг.6C - блок-схема, иллюстрирующая рабочие параметры процесса переупорядочения ячеек в дочерние последовательности и на уровни зависимости, как изображено в примерных вариантах осуществления фиг.6A и фиг.6B, согласно другим вариантам осуществления настоящего изобретения.

Фиг.7 иллюстрирует обработку ячеек, изображенных на фиг.4, двумя отдельными механизмами повторного вычисления, а также очередь ячеек, которые должны быть переупорядочены для каждого из механизмов повторного вычисления согласно варианту осуществления настоящего изобретения.

Фиг.8 изображает представление неоптимального переупорядочения ячеек, поставленных в очередь фиг.7, согласно варианту осуществления настоящего изобретения.

Фиг.9 иллюстрирует код программы для синхронизации потоков механизмов повторного вычисления, изображенных на фиг.7, согласно варианту осуществления настоящего изобретения.

Фиг.10A - блок-схема, иллюстрирующая рабочие параметры процесса инициации оценки значений и формул в ячейках, изображенных на фиг.2, согласно варианту осуществления настоящего изобретения.

Фиг.10B - блок-схема, иллюстрирующая рабочие параметры процесса приостановки или запуска потока управления и/или асинхронных потоков механизмов повторного вычисления, изображенных на фиг.7, согласно варианту осуществления настоящего изобретения.

Фиг.11 - блок-схема, иллюстрирующая рабочие параметры процесса переупорядочения ячеек потоком управления и асинхронными потоками механизмов повторного вычисления, изображенных на фиг.7, согласно варианту осуществления настоящего изобретения.

Фиг.12 - блок-схема, иллюстрирующая рабочие параметры процесса для обеспечения возможности переупорядочения потоком управления ячеек из очередей, изображенных на фиг.7, для работы на формулах только потока управления и для повторного отображения ячеек согласно варианту осуществления настоящего изобретения.

Фиг.13 иллюстрирует логическое представление переупорядочения формулы потока управления на следующий уровень зависимости согласно варианту осуществления настоящего изобретения.

Фиг.14A иллюстрирует обработку циклических формул при многопоточной обработке согласно варианту осуществления настоящего изобретения.

Фиг.14B - блок-схема, иллюстрирующая рабочие параметры процесса переупорядочения последовательности повторного вычисления для возможного обнаружения циклической ссылки и оценки, как изображено в примерном варианте осуществления фиг.14A, согласно другим вариантам осуществления настоящего изобретения.

Фиг.15 изображает примерную вычислительную систему, в которой могут быть реализованы варианты осуществления настоящего раскрытия.

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Теперь согласно этому раскрытию, будут более полно описаны примерные варианты осуществления согласно приложенным чертежам, на которых изображены определенные варианты осуществления. Однако варианты осуществления могут быть реализованы во многих различных видах согласно другим аспектам и включение определенных вариантов осуществления в это раскрытие не должно рассматриваться как ограничение указанных аспектов до изложенных здесь вариантов осуществления. Скорее, варианты осуществления, изображенные на чертежах, включены для обеспечения полного и завершенного раскрытия, которое полностью передает предусмотренный контекст для специалистов в данной области техники. В отношении чертежей, изображенные на них подобные структуры и элементы обозначены подобными ссылочными позициями. Для изображения дополнительных компонентов или операций могут использоваться пунктирные линии. Пунктирные линии могут использоваться также для изображения логического представления или перемещения ячейки из одного местоположения в другое.

На фиг.1 изображена среда 100 для обработки повторных вычислений электронной таблицы количеством “N” процессоров и соответствующих программных потоков. В варианте осуществления система 100 содержит модуль 102 обработки, который включает в себя количество "N" доступных процессоров в операционной системе, каждый из которых содержит функционирующий на нем механизм 104 повторного вычисления ("механизм recalc"). Система 100 дополнительно содержит базу 116 данных и модуль 114 Ввода/Вывода или приема/передачи, действующий для приема и передачи данных из базы 106 данных, а также для осуществления связи с модулем 112 управления загрузкой. В свою очередь, модуль управления загрузкой осуществляет связь с модулем 110 обнаружения границ, который определяет диапазон и область "грязных" ячеек, или тех ячеек, для которых требуется повторное вычисление, так как они зависят от измененного содержимого в другой ячейке или поддерживают его. В варианте осуществления “грязные” ячейки повторно вычисляют в случае приема команды на повторное вычисление из модуля 114 приема/передачи.

В приложении электронных таблиц, использующем многопроцессорную среду системы 100, необходимо определить количество процессоров, доступных в операционной системе. Фиг.2 изображает основную последовательность инициации операций 200, выполняемых системой, изображенной на фиг.1, для загрузки или вызова приложения электронных таблиц и определения количества процессоров для использования им. Инициируют операцию 202 Начала после осуществления связи с модулем 112 управления загрузкой, при этом загружают приложение электронных таблиц операцией 204 загрузки приложения. В варианте осуществления, где используют несколько процессоров и соответственно несколько программных потоков для оценки элементов или элементов "ENT" при последовательном вычислении электронной таблицы, требуется синхронизировать оценку указанных ENT несколькими процессорами. Соответственно, операция 206 определения определяет количество процессоров и, соответственно, механизмов 104 повторного вычисления в операционной системе. Операция 208 сохранения сохраняет определенное количество процессоров и их позиций доступа в базе 116 данных. В варианте осуществления используемые процессоры являются отдельными процессорами, хотя в другом варианте осуществления они являются одним или большим количеством внедренных сопроцессоров на одной микросхеме. В свою очередь, в операции 209 выделения каждому процессору выделяют механизм повторного вычисления, и затем управление процессом 200 переходит к операцию 210 возврата.

Теперь согласно фиг.3 процесс 300 повторного вычисления начинается с операции 302 начала, которую инициируют в ответ на вычисление вручную или автоматическое вычисление или на запрос на повторное вычисление, для обработки последовательного вычисления внутри электронной таблицы, работающей в системе 100, изображенной на фиг.1. Запрос на повторное вычисление из операции 302 начала принимает модуль 114 приема/передачи, и в соответствии с запросом данные извлекаются из базы 116 данных. В варианте осуществления операцию 302 начала запускают посредством запроса вручную пользователем на повторное вычисление отображенной электронной таблицы. В другом варианте осуществления операцию 302 начала запускают автоматически посредством запроса из процедуры вызова или при изменении пользователем значения или формулы в ENT или добавлении дополнительного ENT в электронную таблицу. Независимо от определенного механизма запуска, запрос на повторное вычисление идентифицируют или относительно него принимают решение в операции 304. После операции 304 принятия решения определяют область и диапазон для запроса на повторное вычисление в операции 306. В варианте осуществления это относится только к одному ENT. В другом варианте осуществления это относится к массиву элементов ENT, которые являются зависимыми от измененного содержимого ячейки или вспомогательными для него, то есть к "грязным" ENT. Из операции 306 определения процесс 300 переходит к операции 308 повторного вычисления, в которой повторно вычисляют “грязные” ячейки, согласно вариантам осуществления настоящего изобретения. После завершения повторного вычисления управление переходит к операции 310 возврата, которая возвращает функционирование к коду вызова или пользовательскому интерфейсу.

Фиг.4 изображает обычную электронную таблицу 400, которая может быть повторно вычислена с использованием процесса, описанного выше, согласно фиг.3. В этом примерном представлении электронной таблицы 3x3 ячейки А1 и B1 в строке 402 изображены с примерными значениями "=1". Ячейки A2 и B2 в строке 404 изображены формулами =A1 и =B1, соответственно, которые представляют формулы, зависимые от А1 и B1. Подобным образом, ячейки A3 и B3 в строке 406 изображены формулами =A2 и =B2 соответственно, которые представляют формулы, зависимые от A2 и B2. В заключение, ячейка C3 изображена формулой =A3+B3, означающей, что она является зависимой от A3 и B3. Как отмечено выше, содержимое ячеек А1-C3 может содержать значения или формулы, которые должны быть вычислены или повторно вычислены, и, соответственно, содержимое каждой ячейки определено как элемент или элемент "ENT". Например, формула "=A3+B3" является элементом ENT, расположенным в ячейке C3.

После загрузки или вызова электронной таблицы 400 системой 100, изображенной на фиг.1, процессоры начинают упорядочивать элементы ENT в единую последовательность вычислений в последовательном порядке на основе непосредственно элементов в электронной таблице. Фиг.5 иллюстрирует указанную единую последовательность вычислений, упорядоченную от А1 до C3, для электронной таблицы 400, изображенной на фиг.4. Исключительно в виде примера элементы ENT в ячейках А1-C3, возможно, были введены в электронную таблицу 400 в порядке А1, A2, A3, B1, B2, B3 и, в заключение, C3. При этом первоначальном упорядочении элементов ENT в единую последовательность код программы размещает первый ENT (то есть в рассматриваемом здесь примерном варианте А1) в крайней правой позиции последовательности вычислений (calc). Следующие ENT добавляют в последовательном порядке справа налево и заканчивают C3.

При переходе к оценке элементов ENT в единой последовательности 500 вычислений код вычислений (calc) начинает с C3 и определяет, что формула A3+B3 зависит от формул в ячейках A3 и B3. Затем сначала при рассмотрении ячейки A3 (так как это первая названная ячейка в формуле) определяют, что ячейка A3 является "грязной" или ожидающей вычисления. В этом варианте осуществления ENT "A3+B3" называется "зависимой" формулой, и формула в ячейке A3 называется "вспомогательной" формулой. В варианте осуществления настоящего изобретения единую последовательность 500 вычислений переупорядочивают для создания объединенной последовательности зависимых и вспомогательных формул, организованных в структуру дерева с использованием дочерних последовательностей внутри объединенной последовательности. В варианте осуществления зависимую формулу, например C3, определяют как дочернюю для первой вспомогательной формулы, например A3. Дополнительно, первая вспомогательная формула может быть сделана дочерней для второй вспомогательной формулы, от которой она зависит.

После того как C3 перемещают так, чтобы она была дочерней для A3, оценивают следующую ячейку в единой последовательности, а именно B3 в примерном варианте осуществления, изображенном на фиг.5. При попытке оценить B3, код вычисления (calc) обнаруживает, что B3 является зависимой от ячейки B2 и что B2 является "грязной". Соответственно B3 становится дочерней для B2. Подобным образом, код осуществляет попытку вычисления следующей ячейки, то есть B2, и определяет, что B2 зависит от B1. Соответственно, B2 становится дочерней для B1 и, так как B3 является дочерней для B2, формируют полную дочернюю последовательность B1 B2 и B3 (изображенную как дочерняя последовательность 602 в последовательности 600 на фиг.6A). Затем код вычисления (calc) осуществляет попытку оценить A3 и определяет, что A3 (которая имеет дочернюю С3, как описано выше) является зависимой от вспомогательной формулы A2, которая сама является зависимой от А1. Соответственно, формируют дочернюю последовательность А1, A2, A3 и С3. Примерное представление этой дочерней последовательности изображено в виде дочерней последовательности 604 на фиг.6A.

Хотя последовательность 604 изображает дочернюю последовательность А1, A2, A3 и С3, в другом примерном варианте осуществления этого изобретения, изображенном на фиг.6B, изображена подобная дочерняя последовательность 610, в которой удалена С3, причем согласно другому варианту осуществления изобретения С3 включают в ее собственную последовательность 612, расположенную на отдельном "уровне зависимости" 620. Действительно, на фиг.6B изображены два отдельных уровня зависимости, а именно уровень (618) зависимости #1, и уровень (620) зависимости #2. Каждый уровень зависимости содержит элементы ENT, которые, кроме тех, которые являются зависимыми от вспомогательной формулы в дочерней последовательности внутри одного уровня зависимости, зависят только от элементов ENT на предыдущих уровнях зависимости. Конфигурация в таком варианте осуществления обеспечивает возможность обработки одним или большим количеством процессоров элементов ENT по уровню зависимости в непрерывном режиме без необходимости ожидания вычисления невычисленных вспомогательных элементов ENT.

Преимущества отдельных уровней зависимости могут быть продемонстрированы примерным вариантом осуществления последовательности 600 вычислений, в которой С3 является дочерней для A3, которая в свою очередь является дочерней для A2 и А1. Как изображено на фиг.4, С3 зависит от суммы формул в A3 и B3. Соответственно, С3 является зависимой и от A3 и от B3. При вычислении B3 перед попыткой оценить С3 в дочерней последовательности 604 кодом вычисления (calc), не будет задержки, когда код вычисления (calc) доходит до С3 (то есть код вычислений (calc) может незамедлительно вычислить С3, так как и A3 и B3 уже будут вычислены). Соответственно, в таком варианте осуществления С3 может оставаться в виде части дочерней последовательности 604. Однако там, где B3 не вычисляют перед оценкой С3 кодом вычисления (calc), код вычисления (calc) не будет обеспечивать возможность вычисления С3. Следовательно, С3 остается невычисленной до тех пор, пока остается невычисленной B3. Соответственно, обработка дочерней последовательности 604 должна быть приостановлена или остановлена, что обусловлено зависимостью C3 от B3. Такие зависимости обеспечивают возможность создания нерациональных ситуаций при обработке повторных вычислений. Соответственно, вариант осуществления обеспечивает извлечение С3 (612) из уровня #1 зависимости (618) на уровень #2 зависимости (620), как изображено в объединенной последовательности 606 вычислений (calc) на фиг.6B.

В варианте осуществления, где доступны несколько процессоров, перемещение С3 на новый уровень зависимости обеспечивает возможность завершения обработки этой последовательности вторым процессором, работающим на дочерней последовательности 610, и перехода им к обработке другого ENT или дочерней последовательности внутри уровня зависимости #1, в то время как первый процессор продолжает обработку дочерней последовательности 608. На фиг.6В эти несколько процессоров изображены в виде механизмов (614 и 616 соответственно) повторного вычисления, так как каждый процессор содержит работающий на нем механизм повторного вычисления. Хотя на фиг.2 изображено два механизма повторного вычисления, согласно варианту осуществления настоящего изобретения, для операций вычисления и повторного вычисления может быть использовано любое количество "N" процессоров, как изображено эллипсами 104 на фиг.1.

Фиг.6C иллюстрирует процесс 622 выполнения переупорядочения ENT и их перемещения на следующий уровень зависимости, если он существует, согласно варианту осуществления настоящего изобретения. Инициируют операцию 624 Начала в ответ на загрузку ячеек в программу 400 электронных таблиц и запрос на повторное вычисление. От операции 624 начала процесс 622 переходит к операции 626 упорядочения, в которой элементы ENT упорядочивают в единую последовательность вычислений на основе порядка их элементов в программе 400 электронных таблиц, как описано выше. Затем операция 628 оценки осуществляет попытку оценить первую формулу в единой последовательности вычислений. После попытки оценить первую формулу процесс 622 переходит к операции 630 запроса, которая определяет, является ли первая формула зависимой от вспомогательной формулы. Если первая формула является зависимой от вспомогательной формулы, то последовательность операций идет по ответвлению ДА к операции 634 перемещения, которая перемещает первую зависимую формулу в позицию дочерней для вспомогательной формулы. Если первая формула не является зависимой от вспомогательной формулы, то последовательность операций идет по ответвлению НЕТ к операции 632 оценки, и оценивают первую формулу.

От операции 634 перемещения процесс 622 переходит к операции 636 запроса, которая определяет, является ли первая формула также зависимой от второй невычисленной формулы. Если операция 636 запроса определяет, что первая формула является зависимой от второй невычисленной формулы, то последовательность операций идет по ответвлению ДА к операции 642 перемещения, которая перемещает первую зависимую формулу на следующий уровень зависимости. Затем операция 644 запроса определяет, существуют ли другие формулы для оценки в последовательности вычислений, и, если существуют, то идет по ответвлению ДА к операции 628 оценки. Если операция 644 запроса определяет, что не существует других формул для оценки, то последовательность операций идет по ответвлению НЕТ к операции 646 завершения, которая заканчивает процесс 622. Если операция 636 запроса определяет, что первая зависимая формула не является зависимой от второй невычисленной вспомогательной формулы, то последовательность операций идет по ответвлению НЕТ к операции 638 запроса, которая определяет, имеет ли первая вспомогательная формула также вторую зависимую формулу. Если операция запроса определяет, что первая вспомогательная формула не имеет второй зависимой формулы, то последовательность операций идет по ответвлению НЕТ к операции 632 оценки. С другой стороны, если операция 638 запроса определяет, что первая вспомогательная формула имеет также вторую зависимую формулу, то последовательность операций идет по ответвлению ДА к операции 640 перемещения, в которой первую и вторую зависимые формулы перемещают на следующий уровень зависимости. От операции 640 перемещения процесс 622 переходит к операции 644 запроса для определения, требуется ли оценка других формул, и процесс продолжается, как описано выше.

При том, что переупорядочение элементов ENT, описанное согласно фиг.6A-6C, имело отношение к переупорядочению в общем, безотносительно количества процессоров (то есть к использованию одного или большего количества процессоров), фиг.7, в частности, иллюстрирует переупорядочение 700 единой последовательности вычислений для электронной таблицы 400 посредством использования нескольких механизмов повторного вычисления и асинхронных потоков. Для синхронизации различных потоков и механизмов повторного вычисления применяют поток 702 управления. В примерном варианте осуществления системы 700 применяют два механизма 704 и 712 повторного вычисления; однако другие варианты осуществления могут содержать любое количество механизмов повторного вычисления и соответствующих операций многопоточной обработки.

Согласно примерному варианту осуществления, изображенному на фиг.7, поток обработки механизма 1 (704) повторного вычисления осуществляет попытку оценить С3 в единой последовательности 708 вычислений. Так как С3 является зависимой от A3 и B3, которые еще не вычислены, С3 пока не может быть вычислена. Следовательно, механизм 1 повторного вычисления перемещает С3 в свою очередь 706 зависимых и вспомогательных формул. С3 включают в список как зависимую формулу, и A3 включают в список как вспомогательную формулу для С3. Затем программный поток механизма 2 (712) повторного вычисления осуществляет попытку оценить B3. Не обладая возможностью оценить эту зависимую формулу, механизм 2 повторного вычисления перемещает зависимую В3 и ее вспомогательную формулу B2 в свою собственную очередь 710 зависимых и вспомогательных формул. Этот процесс продолжается до тех пор, пока механизмы повторного вычисления не осуществят попытку оценить каждый ENT в единой последовательности 708 вычислений.

После того как каждый ENT в последовательности 708 был оценен или была предпринята попытка его оценить, очереди 706 и 710 посредством потока 702 управления переупорядочивают в дочерние последовательности на основе их отношений зависимости. Подобно описанной выше дочерней последовательности 604, на фиг.8 изображена дочерняя последовательность 804 с элементами ENT А1, A2, A3 и С3. Элементы ENT B1, B2 и B3 изображены в дочерней последовательности 802. Обе указанные дочерние последовательности первоначально изображены как размещенные на уровне #1 (806) зависимости на фиг.8. Согласно варианту осуществления механизм 1 (704) повторного вычисления обрабатывает дочернюю последовательность 802, состоящую из B1, B2 и В3. Затем, в то время как механизм 1 повторного вычисления начинает обработку дочерней последовательности 802, механизм 2 повторного вычисления начинает обработку дочерней последовательности 804. Согласно этому примерному варианту осуществления предполагается, что механизм 1 повторного вычисления заканчивает обработку В3 в дочерней последовательности 802 до достижения механизмом 2 повторного вычисления С3 из дочерней последовательности 804. В таком случае может быть осуществлена оценка С3, так как вспомогательные формулы A3 и Б3 уже были вычислены. В этом варианте осуществления на фиг.8 С3 изображают размещенной на уровне #1 (806) зависимости, и уровень #2 зависимости (808) изображают пустым. Однако в другом варианте осуществления существует возможность (по многим причинам), что механизм 1 повторного вычисления не обеспечен возможностью оценить В3 перед попыткой механизмом 2 повторного вычисления оценить С3. В таком случае С3 должна была остаться невычисленной, и механизм 2 повторного вычисления должен быть остановлен, ожидая завершения обработки В3 механизмом 1 повторного вычисления. Такая остановка препятствует обработке механизмом 2 повторного вычисления других элементов ENT и дочерних последовательностей, которые могут существовать внутри первого уровня зависимости (хотя такие дополнительные последовательности не изображены в примерном варианте осуществления фиг.8). Остановка механизма повторного вычисления является нерациональным использованием возможностей многопоточной обработки многопроцессорной системы (то есть где операции повторного вычисления, необходимые для механизма 2 повторного вычисления, зависят от скорости обработки единого механизма 1 повторного вычисления). Соответственно вариант осуществления, изображенный на фиг.8, не является оптимальным в отношении переупорядочения ячеек. Напротив, оптимальное переупорядочение должно быть представлено, как примерный вариант осуществления, изображенный на фиг.6B, и описанный выше, согласно фиг.6В.

В то время как на фиг.8 изображено неоптимальное переупорядочение 800 элементов ENT, при котором С3 остается на уровне #1 (806) зависимости, в других вариантах осуществления (где Б3 остается невычисленным во время оценки С3) должно требоваться перемещение С3 на уровень #2 (808) зависимости. В одном варианте осуществления используют следующие правила управления перемещением элемента ENT на следующий уровень зависимости:

(1) Осуществить попытку сделать зависимую формулу дочерней для вспомогательной формулы.

(2) Если зависимая формула уже является дочерней для другой формулы, то зависимую формулу ставят в очередь для следующего уровня зависимости; или

если вспомогательная формула, от которой уже зависит зависимая формула, имеет дочернюю, то зависимые формулы ставят в очередь для следующего уровня зависимости.

(3) Если формула содержит функцию, которая должна быть оценена потоком управления, то формулу (определена, как "формула потока управления") перемещают на следующий уровень зависимости. Исключительно в виде примера, потоком управления должны оцениваться следующие функции:

(a) функция INDIRECT;

(b) функция GETPIVOTDATA;

(c) функция INFO;

(d) функция ADRESS;

(e) функции, определяемые пользователем, (UDF).

Теперь согласно фиг.9 изображен примерный вариант осуществления кода 900 программы для запуска и приостановки асинхронных потоков механизмов 1 и 2 повторного вычисления, изображенных на фиг.7, согласно варианту осуществления настоящего изобретения. Поток 902 управления управляет запуском асинхронных потоков. Первоначально счетчик 906 устанавливают в количество процессоров, определенных операцией 206 определения. Счетчиком 906 может быть любой вид счетчика. В примерном варианте осуществления счетчик 906 может быть определен как ISpinning. Вне зависимости от термина или вида используемого счетчика счетчик 906 в потоке 902 управления (CT) устанавливают в количество процессоров, определенных доступными для многопоточной обработки. В примерном варианте осуществления фиг.9 счетчик 906 для механизмов 910 и 920 повторного вычисления, соответственно, устанавливают в значение "2". Дополнительно, устанавливают в ноль ("0") индекс 904 потока управления, например, int ientNext, и устанавливают в "0" индекс 914 и 924 каждого механизма повторного вычисления, int iENT. Как описано ниже, указанные индексы управляют указателями для элементов ENT 912 и 922. Значение "0" индекса является индексом для первой ячейки, то есть С3, слева от единой последовательности 918 вычисления.

Фиг.10А и 10В иллюстрирует этапы 1000 работы по запуску и остановке операций асинхронных потоков механизмов 1 (910) и 2 (920) для оценки единой последовательности 918 вычислений. Согласно фиг.10, в ответ на загрузку или вызов инициируют операцию 1002 Начала вычислений для оценки электронной таблицы, такой как электронная таблица 400, изображенная на фиг.4. В операции 1004 установки счетчик 906 устанавливают в количество механизмов повторного вычисления. Затем, в операции 1006 назначения поток 902 управления устанавливает в "0" индексы, 914 и 924, механизмов 1 и 2 повторного вычисления, соответственно, так чтобы каждому потоку было назначено начинать оценку с первого ENT. Затем поток 902 управления запускает на каждом механизме повторного вычисления события 916 и 926 для активизации потоков для осуществления обработки в операции 1008 запуска. Примерными вариантами события, где поток 902 управления может запускать событие механизма повторного вычисления, являются вызов или загрузка приложения. После запуска каждый механизм повторного вычисления выполняет операцию 1010 приращения с блокировкой для сохранения потока. Например, механизм 910 повторного вычисления начинает указанную операцию 1010 приращения с блокировкой посредством добавления "1" к индексу 904 потока управления и приема предыдущего значения индекса 904, то есть "0" в этом варианте осуществления, возвращаемого из потока 902 управления. Разность между значением индекса 914 первого механизма повторного вычисления и значением индекса 904 потока управления, возвращенным из потока 902 управления, является значением, на которое механизм 1 повторного вычисления должен выполнять итерации вниз по единой последовательности 918 вычислений. В этом примерном варианте осуществления механизм 1 (910) повторного вычисления осуществляет приращение индекса 904 потока управления с значения "0" в значение "1". Так как предыдущее значение индекса 904 потока управления было "0", то механизм 1 (910) повторного вычисления принимает значение "0", сравнивает его со значением своего собственного индекса 914, например, "0", согласно этому примерному варианту осуществления, для определения разности между этими двумя значениями, то есть "0" минус "0" равняется "0", и получает значение "0". Значение "0" требует оценки механизмом 1 (910) повторного вычисления первого ENT (то есть С3) последовательности 918 вычислений.

Подобным образом, механизм 2 (920) повторного вычисления выполняет операцию приращения с блокировкой для сохранения потока, при которой он увеличивает индекс 904 потока управления с "1" до "2", и принимает возвращаемое предыдущее значение индекса 904 потока управления, то есть "1", в этом примерном варианте осуществления. Затем механизм 2 (920) повторного вычисления сравнивает это возвращенное значение "1" индекса 904 потока управления со значением своего собственного индекса, то есть "0" в этом примерном варианте осуществления, и вычисляет разность между этими двумя значениями "1". Значение "1", соответственно, требует оценки механизмом 2 (920) повторного вычисления второго ENT (то есть Б3) последовательности 918 вычислений.

Согласно варианту осуществления указанную операцию приращения с блокировкой для сохранения потока продолжают до окончания последовательности зависимости. После выполнения операции 1010 приращения с блокировкой каждый механизм повторного вычисления начинает оценку назначенного ENT в операции 1012. Запустив асинхронные потоки для оценки последовательности 918, поток 902 управления на этапе 1014 приостанавливает свои собственные операции и ожидает своего собственного события 908 для запуска. Затем процесс 1000 переходит к операции 1016 возврата.

В варианте осуществления операции механизма повторного вычисления могут быть приостановлены отдельно непосредственно механизмом повторного вычисления. В другом варианте осуществления механизм повторного вычисления может затребовать приостановку всех асинхронных потоков. В первом варианте осуществления асинхронный поток приостанавливает свое действие по достижении конца уровня зависимости. В другом варианте осуществления асинхронный поток может быть приостановлен при заполнении очереди, или буфера, этого потока зависимыми и вспомогательными формулами. Другие варианты