Многопоточная обработка электронных таблиц с использованием уровней зависимости
Изобретение относится к области многопоточной обработки электронных таблиц. Техническим результатом является повышение производительности работы приложений электронных таблиц в многопроцессорных окружениях. Раскрыт способ для обработки последовательных вычислений в приложениях электронных таблиц с использованием нескольких процессоров, каждый из которых имеет отдельный механизм повторного вычисления. Единая последовательность вычислений может быть переупорядочена в объединенную последовательность, где вспомогательные формулы и зависимые формулы организованы в иерархии дерева дочерних последовательностей. Дополнительно, объединенную последовательность разделяют на уровни зависимости, где при переупорядочении элементы на каждом уровне зависимости могут быть перемещены на следующий уровень зависимости. Если элемент внутри уровня зависимости является зависимым от другого элемента, который не обнаружен внутри его собственной дочерней последовательности, объединенную последовательность упорядочивают так, что элемент является зависимым только от элемента на предыдущем уровне зависимости. Дополнительно, уровни зависимости обеспечивают возможность выполнения потоком управления операций только потока управления, при этом поддерживаются возможности многопоточной обработки. 2 н. и 15 з.п. ф-лы, 17 ил.
УРОВЕНЬ ТЕХНИКИ
Для анализа данных стало распространенным использование приложений электронных таблиц. Дополнительно, так как деловая активность все более зависит от указанных приложений для сложного вычисления данных, возникла потребность в более быстрой и более эффективной обработке указанных приложений. Примером такого приложения электронных таблиц является Microsoft ExcelTM. В приложениях электронных таблиц стало обычным наличие в одной ячейке формулы, определенной как "зависимая" формула, которая зависит от содержимого или формулы в другой ячейке, определенной как "вспомогательная" формула. При изменении содержимого ячейки может быть запущена операция повторного вычисления ("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 возврата.
В варианте осуществления операции механизма повторного вычисления могут быть приостановлены отдельно непосредственно механизмом повторного вычисления. В другом варианте осуществления механизм повторного вычисления может затребовать приостановку всех асинхронных потоков. В первом варианте осуществления асинхронный поток приостанавливает свое действие по достижении конца уровня зависимости. В другом варианте осуществления асинхронный поток может быть приостановлен при заполнении очереди, или буфера, этого потока зависимыми и вспомогательными формулами. Другие варианты осуществления могут содержать другие причины для приостановки асинхронного потока. Приведенные здесь примерные варианты предназначены служить исключительно в виде примерных вариантов осуществления. В дополнительном варианте осуществления асинхронный поток может затребовать приостановки всех потоков (например, там, где асинхронным потоком обнаружена формула потока управления).
После приведенного выше описания запуска операций потока, согласно фиг.10A, описан процесс 1018 "приостановки" для приостановки, или остановки, отдельных операций асинхронных потоков, согласно фиг.10B, согласно примерному варианту осуществления. Согласно варианту осуществления настоящего изобретения блок-схема, изображенная на фиг.10B, иллюстрирует переход операций между двумя потоками. В другом варианте осуществления потоки могут функционировать одновременно. Блок-схема, изображенная на фиг.10B, предназначена служить исключительно в виде примерного варианта осуществления и никоим образом не должна рассматриваться как ограничивающая операции потоков. Согласно фиг.10B, как описано выше, поток может приостановить свои операции, если он обнаруживает, что достигнут конец уровня зависимости. В другом варианте осуществления поток может приостановить свои операции, если он обнаруживает, что заполнены его очередь или буфер. Соответственно, от операции 1020 начала поток переходит к операции 1024 запроса, которая определяет, был ли достигнут конец уровня зависимости, или был ли заполнен буфер для механизма #1 повторного вычисления. Если операция 1024 запроса определяет, что конец уровня зависимости не был достигнут и что очередь для этого потока не заполнена, последовательность операций переходит по НЕТ к операции 1026 продолжения, при этом поток продолжает оценивать элементы ENT и выполнять итерации вниз для последовательности вычислений. С другой стороны, если операция 1024 запроса определяет, что был достигнут конец уровня зависимости или что буфер для этого потока заполнен, поток переходит по ДА к операции 1028 уменьшения счетчика. Операция уменьшения счетчика уменьшает счетчик 906 потока управления. При приостановке своих собственных операций механизм повторного вычисления должен, среди других функций, уменьшить счетчик потока 906 управления. Если счетчик 906 имеет значение, превышающее "0", то поток должен функционировать или оставаться активизированным. Однако когда значение счетчика равно "0", все потоки приостанавливают и запускают событие 908 потока 902 управления. При уменьшении счетчика 906 потока управления механизм #1 повторного вычисления приостанавливают в операции 1030 ожидания или, другими словами, переводят в режим ожидания. Затем операция 1032 запроса определяет, равен ли счетчик 906 потока управления "0". Если счетчик 906 имеет значение "0", то последовательность операций идет по ответвлению ДА для запуска операции 908 события потока управления в операции 1034, так как значение "0" указывает, что все асинхронные потоки приостановлены. Если счетчик 906 имеет ненулевое значение, то последовательность операций идет по ответвлению НЕТ к операции 1036 перехода, при которой управление передают механизму #2 повторного вычисления. Механизм #2 повторного вычисления проходит через этапы 1038-1048, которые подобны описанным выше для механизма #1 повторного вычисления.
Согласно варианту осуществления представленного раскрытия изображен процесс 1100 выполнения итераций по последовательности вычислений для определения необходимого переупорядочения и обнаружения формул потока управления, если они существуют. Как описано выше, примерный вариант осуществления настоящего изобретения, изображенный на фиг.11, иллюстрирует переход операций между двумя потоками. В другом варианте осуществления потоки могут работать одновременно.
Блок-схема, изображенная на фиг.11, предназначена служить исключительно в виде примерного варианта осуществления и никоим образом не должна рассматриваться как ограничивающая операции потоков. Согласно фиг.11, инициируют операцию 1102 начала после запуска событий 1008 каждого механизма повторного вычисления. От операции 1102 начала последовательность операций переходит к операции 1104 приращения с блокировкой механизма #1 повторного вычисления. Затем механизм #1 повторного вычисления выполняет итерации вниз по последовательности вычислений в операции 1106 выполнения итераций до вычисленного значения ENT, назначенного посредством операции 1104 приращения с сохранением потока. При достижении назначенного ENT последовательность операций переходит к операции 1112 запроса, которая определяет, был ли достигнут конец уровня зависимости или заполнены ли очередь (или буфер) асинхронного потока. При обнаружении конца уровня зависимости или при определении, что очередь асинхронного потока заполнена, асинхронный поток приостанавливает свои собственные операции в операции 1116 приостановки. Если все указанные позиции, требующие приостановки, отсутствуют, то процесс 1100 переходит к операции 1114 запроса, которая определяет, является ли формула формулой потока управления. При обнаружении формулы потока управления последовательность операций идет по ответвлению ДА к операции 1115 постановки в очередь, которая осуществляет постановку в очередь формулы потока управления в отдельный буфер, или отдельную очередь, состоящие только из таких формул. Если операция 1114 запроса определяет, что формула не является формулой потока управления, то последовательность операций идет по ответвлению НЕТ к операции 1120 запроса, которая определяет, является ли формула в назначенном ENT зависимой от невычисленного ENT. Если операция 1120 запроса определяет, что формула является зависимой от невычисленного ENT, то последовательность операций идет по ответвлению ДА к очереди 1 в операции 1122, в которой зависимые и вспомогательные формулы помещают в надлежащую очередь. Если операция 1120 запроса определяет, что формула не является зависимой от невычисленного ENT, то последовательность операций идет по ответвлению НЕТ для оценки формулы в операции 1118, которая возвращает значение.
После операций 1118 и/или 1122 оценки и постановки в очередь процесс 1100 переходит к операции 1124, в которой операции переходят к механизму #2 повторного вычисления. Второй механизм повторного вычисления выполняет этапы 1126-1142, которые подобны описанным выше в отношении механизма #1 повторного вычисления операциям 1104-1124.
Теперь согласно фиг.12 изображен процесс 1200, касающийся операций потока управления для переупорядочения последовательности вычислений в объединенную переупорядоченную последовательность согласно варианту осуществления настоящего изобретения. В ответ на запуск события потока управления инициируют операцию 1202 Начала. От операции 1202 начала последовательность операций переходит к операции 1203 повторного отображения, которая повторно отображает ячейки электронной таблицы 400. После операции 1203 повторного отображения процесс 1200 переходит к операции 1204 запроса, которая определяет, существуют ли элементы в очередях механизмов повторного вычисления. Если операция 1204 запроса определяет, что такие элементы существуют, то последовательность операций идет по ответвлению ДА к операции 1210 переупорядочения. Операция 1210 переупорядочения переупорядочивает зависимые и вспомогательные формулы в дочерних последовательностях внутри объединенной последовательности. После завершения этого переупорядочения операция 1218 запроса определяет, были ли созданы дочерние (последовательности). Если были, то необходимо вновь выполнить операцию повторного вычисления по уровню зависимости, содержащему эти новые дочерние последовательности. Соответственно, если были созданы дочерняя (последовательность) или дочерние (последовательности), последовательность операций идет по ответвлению ДА к операции 1224 сброса, которая сбрасывает индексы и указатели механизмов повторного вычисления, так чтобы вновь начать с начала этого уровня зависимости. Отсюда процесс 1200 переходит к операции 1230 активизации, которая запускает события асинхронных потоков. Указанные потоки выполняют операции повторного вычисления на переупорядоченной последовательности. После запуска механизмов повторного вычисления поток управления приостанавливает свои собственные операции в операции 1232 ожидания.
Если операция 1218 запроса определяет, что при переупорядочении не были созданы дочерние (последовательности), элемент или элементы в очередях должны были быть перемещены на следующий уровень зависимости, как представлено операцией 1220. Если не были созданы дочерние (последовательности), то не требуется повторного вычисления элементов ENT внутри текущего уровня зависимости. Вместо этого сбрасывают индексы и указатели асинхронных потоков, а также индекс управления асинхронным потоком, в операции 1222 сброса для следующего уровня зависимости. Затем последовательность операций переходит к операции 1226 запроса для определения, существуют ли формулы потока управления на следующем уровне зависимости. Если операция 1226 запроса определяет, что формулы потока управления на следующем уровне зависимости существуют, то последовательность операций идет по ответвлению ДА к операции 1228 выполнения, которая обеспечивает возможность работы потока управления на этой формуле(ах). После оценки этих формул последовательность операций переходит к операции 1230 активизации асинхронных потоков, которая запускает события асинхронных потоков и обрабатывает этапы 1230 и 1232, как описано выше. Если операция 1226 запроса определяет, что таких формул не существует, то последовательность операций идет по ответвлению НЕТ к операции 1230 активизации, и процесс 1200 проходит по этапам 1230 и 1232, как описано выше.
Если операция 1204 запроса определяет, что не существует элементов в очередях повторного вычисления, то последовательность операций идет по ответвлению НЕТ к операции 1206 запроса, которая определяет, существует ли формула потока управления в связном списке потока 902 управления. Как описано выше, формула потока управления является формулой, которая должна быть оценена потоком управления, а не одним из асинхронных потоков. Если в очередь была поставлена формула потока управления, то последовательность операций идет по ответвлению ДА к операции 1212 перемещения, в которой формулу потока управления перемещают на следующий уровень зависимости в объединенной последовательности. При перемещении формулы потока управления на новый уровень зависимости непосредственно после текущего уровня зависимости может быть продолжена многопоточная обработка, несмотря на необходимость оценки формулы потока управления. От операции 1212 перемещения последовательность операций переходит к операции 1216 запроса, которая определяет, существуют ли другие формулы потока управления. Если существуют другие формулы потока управления, поставленные в очередь, то последовательность операций идет по ответвлению ДА к операции 1206 запроса и повторяет вышеупомянутые этапы. Если операция 1216 запроса определяет, что других формул потока управления не существует, то последовательность операций идет по ответвлению НЕТ к операции 1222 сброса, которая сбрасывает индексы и указатели асинхронных потоков (и соответствующий управляющий индекс потока управления) на следующем уровне зависимости.
Перед приостановкой потоком управления своих операций вначале определяют, в операции 1226 запроса, существуют ли формулы потока управления на следующем уровне зависимости, и затем процесс 1200 проходит через этапы 1226-1232, как описано выше.
Если операция 1206 запроса определяет, что формул потока управления не существует, то последовательность операций идет по ответвлению НЕТ к операции 1222 сброса, которая сбрасывает индексы и указатели для следующего уровня зависимости, и процесс 1200 проходит через этапы 1222-1232, как описано выше.
Тогда как 1206 и 1212 на фиг.12 включают в себя перемещение формулы потока управления на новый уровень зависимости, непосредственно следующий за текущим уровнем зависимости, фиг.13 иллюстрирует логическое представление 1300 этого перемещения. На фиг.13 изображен уровень #1 (1302) зависимости и уровень #2 (1310) зависимости с С3 (1312), размещенной на уровне #2 зависимости. Дополнительно, на уровне #1 зависимости изображена формула потока управления "CT" (1308) (также содержит последовательность 1304 и последовательности 1306). Как описано, для обеспечения возможности выполнения потоком управления формул только потока управления, в варианте осуществления настоящего изобретения формулу 1308 потока управления перемещают в связный список очереди потока управления. Затем, когда запускают поток управления и осуществляют управление операциями и переупорядочение, поток управления перемещает формулу потока управления на новый уровень зависимости, непосредственно следующий за текущим. Примерный вариант осуществления фиг.13, соответственно, изображает перемещение (1320) формулы 1308 потока управления на уровень #2 (1316) зависимости и уровень зависимости, содержащий С3, теперь становится отдельным уровнем #3 (1318) зависимости. В этом варианте осуществления изображена только одна формула потока управления. В другом варианте осуществления несколько формул потока управления могут быть перемещены на новый уровень 1316 зависимости. В виде варианта каждая формула потока управления может быть перемещена на свой собственный новый уровень зависимости, следующий за уровнем #1 (1314) зависимости и расположенный перед уровнем #3 (1318) зависимости.
В вариантах осуществления формулы потока управления перемещают на следующий уровень зависимости, так как поток управления должен быть потоком, работающим в конце уровня зависимости. Перед запуском асинхронных потоков для начала оценок на следующем уровне зависимости поток управления может сначала определять, существуют ли формулы потока управления, которые должны быть выполнены до запуска асинхронных потоков. Перемещение формулы потока управления на отдельный уровень зависимости обеспечивает возможность продолжения многопоточной обработки, при этом одновременно обеспечивая возможность операций только потока управления. Хотя на фиг.13 изображены три уровня зависимости, может существовать любое количество таких уровней, и примерный вид изображенного здесь варианта осуществления никоим образом не предназначен для ограничения количества таких возможных уровней зависимости.
Вариант осуществления настоящего изобретения, который логически представлен на фиг.14A, дополнительно обеспечивает возможность выполнения приложением электронных таблиц с многопроцессорными возможностями вычислений с циклической ссылкой (то есть вычислений, зависимых друг от друга) внутри многопоточной обработки объединенной последовательности вычислений. В электронной таблице 1402 представлены ячейки А1-A3 со случаями циклических ссылок. Другими словами, формула в ячейке А1 является зависимой от A3, которая является зависимой от формулы A2, которая, в свою очередь, сама является зависимой от А1. Для решения этой проблемы циклической ссылки в варианте осуществления настоящего изобретения обеспечивают возможность извлечения ячеек с циклической ссылкой, или отсоединения от объединенной последовательности, и размещения в едином последовательном вычислении, то есть последовательности вычислений calc без дочерних последовательностей или уровней зависимости для вычисления с использованием одного потока. При наличии единого последовательного вычисления, в противоположность объединенному, включающему в себя отношения дочерний (порождающий) и/или уровни зависимости, итерационная функция может выполнять итерационные вычисления на последовательности для схождения к конечному значению. Примерным вариантом такой функции является IterativeCalc 1410; однако согласно варианту осуществления настоящего изобретения для вычисления с циклическими ссылками может быть использован любой вид итерационной функции.
Для создания единого последовательного вычисления для итерационного кругового вычисления вначале ячейки размещают в едином последовательном вычислении 1404, как описано выше (то есть на основе их элемента в электронной таблице 1402). В этом примерном варианте осуществления вначале оценивают В1 и определяют, что она не является зависимой от другой формулы. Затем, действуя вниз по последовательности, A3 определяют зависимой от A2 и помечают, как “In Progress” (“Исполняема в текущий момент”) и удаляют из последовательности вычислений calc, так чтобы она стала дочерней для вспомогательной формулы A2. При перемещении вниз по последовательности 1404 к ENT A2 обнаруживают, что A2 является зависимой от А1. A2, соответственно, помечают, как “In Progress” и удаляют из последовательности 1404 вычислений calc в положение дочерней для вспомогательной формулы А1. При перемещении A2 в положение дочерней для А1, A2 захватывает с собой A3. Затем при перемещении вниз по последовательности 1404 к А1 осуществляют попытку оценить А1. Однако обнаруживают, что А1 является зависимой от A3, так что в 1406 идентифицируют наличие циклической ссылки. А1 помечают, как “In Progress”, и удаляют из последовательности 1404 вычислений calc. В результате А1, A2 и A3 теперь полностью отсоединены от последовательности 1404 вычислений calc, как изображено в переупорядоченной последовательности 1406. Следовательно, в процессе выполнения итераций по последовательности А1, A2 и A3 обработаны не будут. Следовательно, после окончания выполнения итераций по последовательности, А1, A2 и A3 останутся помеченными “In Progress”, или “грязными”. Для обработки этих позиций система отслеживает каждую формулу, которая сделана дочерней для другой формулы в продолжение текущего процесса повторных вычислений. Затем все формулы, которые были сделаны дочерними в продолжение процесса, проверяют для обнаружения, остались ли среди них помеченные или “грязные”. Если остались, что формулу и все ее дочерние (формулы) перемещают в одноуровневую последовательность 1408 вычислений calc, то есть последовательность вычислений calc без дочерних последовательностей или уровней зависимости. Затем вычисляют эту одноуровневую последовательность вычислений calc, изображенную на фиг.14A в 1408, с использованием одного потока. Если в продолжение вычисления для одного потока обнаруживают истинную циклическую ссылку, то вычисление может быть осуществлено итеративно, например, посредством итерационной функции 1410 вычисления.
Теперь, согласно фиг.14B, изображен процесс 1411 переупорядочения последовательности вычислений calc в одноуровневую последовательность вычислений calc для возможного обнаружения циклической ссылки и оценки согласно варианту осуществления настоящего изобретения. После создания единой последовательности 1404 вычислений calc инициируют операции 1412 Начала. От операции 1412 начала последовательность операций переходит к операции 1414 получения, в которой получают первую формулу в последовательности 1404 вычислений calc. Затем операция 1416 оценки оценивает эту формулу. Операция 1418 запроса определяет, является ли формула дочерней для вспомогательной формулы. Если формула является дочерней для вспомогательной формулы, то последовательность операций идет по ответвлению ДА к операции 1420 отслеживания, и дочернюю формулу помечают “In Progress” и продолжают отслеживать системой. Если формула не является дочерней для вспомогательной формулы, то последовательность операций идет по ответвлению НЕТ к операции 1422 запроса, которая определяет, существуют ли другие формулы в последовательности 1404 вычислений calc для обработки. Если существует большее количество формул, то последовательность операций идет по ответвлению ДА к операции 1414 получения, которая перемещается к следующей формуле в последовательности 1404 вычислений calc для оценки. Если других формул не существует, то последовательность операций идет по ответвлению НЕТ к операции 1424 получения отслеживаемой формулы, которая восстанавливает первую (или следующую) формулу, которую отслеживают посредством операции 1420 отслеживания. Затем операция 1426 запроса определяет, остается ли восстановленная отслеживаемая формула помеченной или “грязной”. Если формула остается помеченной, как “грязная”, то последовательность операций идет по ответвлению ДА к операции 1428 одноуровневой последовательности вычислений calc, которая добавляет формулу и все ее дочерние (формулы) в одноуровневую последовательность вычислений calc, как изображено в одноуровневой последовательности 1408 вычислений calc, согласно примерному варианту осуществления настоящего изобретения. Если операция 1426 запроса определяет, что отслеживаемая формула остается “грязной”, то последовательность операций идет по ответвлению НЕТ к операции 1430 запроса, которая определяет, существуют ли другие формулы, которые отслеживались (или помечены, как “In Progress”). Если существуют другие отслеживаемые формулы, то последовательность операций идет по ответвлению ДА к операции 1424 получения первой/следующей отслеживаемой формулы, и повторяют этапы 1426-1430. Если операция 1430 запроса определяет, что другие отслеживаемые формулы не существуют, то последовательность операций идет по ответвлению НЕТ к операции 1432 возврата. После создания одноуровневой последовательности вычислений calc посредством процесса 1411, указанная одноуровневая последовательность вычислений calc (которая создана на этапе 1428 и изображена в виде одноуровневой последовательности 1408 вычислений calc) может быть вычислена с использованием одного потока. Если в продолжение вычисления calc одного потока обнаружена истинная циклическая ссылка, то формулы могут быть вычислены итеративно. Хотя в качестве языка отслеживания в этом возможном варианте осуществления (и при описании фиг.14A) был использован термин “In Progress”, согласно вариантам осуществления настоящего изобретения может быть использован любой механизм маркировки или отслеживания.
Фиг.15 иллюстрирует примерную вычислительную систему 1500, в которой может быть реализовано настоящее изобретение. На фиг.2 изображена вычислительная система 1500, которая содержит, по меньшей мере, один процессор 1502 и действующий на нем, по меньшей мере, один механизм 1518 повторного вычисления. Система 1500 имеет память 1504, в которой находится приложение 1520 электронных таблиц. Вычислительная система 1500 в наиболее базовой конфигурации выделена пунктирной линией 1506 на фиг.15. Дополнительно система 1500 может содержать также дополнительное хранилище (съемное и/или несъемное), включая магнитные или оптические диски или ленту и т.д. Такое дополнительное хранилище проиллюстрировано на фиг.15 съемным хранилищем 1508 и несъемным хранилищем 1510. Компьютерные носители хранения включают в себя энергозависимый и энергонезависимый, съемный и несъемный носитель информации, реализованный любым способом или технологией для хранения информации, такой как инструкции, считываемые компьютером, структуры данных, программные модули или другие данные. Память 1504, съемное хранилище 1508 и несъемное хранилище 1510 являются возможными вариантами компьютерных носителей хранения. Компьютерные носители хранения включают в себя RAM, ROM, EEPROM, флеш-память или другую технологию памяти, CD-ROM, цифровые универсальные диски (DVD) или другое оптическое хранилище, магнитные кассеты, магнитную ленту, магнитное дисковое хранилище или другие магнитные устройства хранения, или любую другую среду, которая может быть использована, например, для хранения необходимой информации вычисления электронных таблиц и к которой может осуществить доступ система 1500 и т.д. Любой такой компьютерный носитель хранения может быть частью системы 1500. В зависимости от конфигурации и вида вычислительного устройства память 1504 может быть энергозависимой, энергонезависимой или некоторой их комбинацией. Среда связи, обычно, воплощает инструкции, считываемые компьютером, структуры данных, программные модули или другие данные в модулированном сигнале данных, таком как несущая волна или другой механизм транспортировки, и включает в себя любую среду доставки информации. Термин "модулированный сигнал данных" означает сигнал, который имеет один или большее количество параметров, установленных или измененных так, чтобы кодировать информацию в сигнале. В виде примерного варианта среды связи включают в себя проводную среду, такую как проводную сеть или прямое кабельное соединение, и беспроводные среды, такие как акустическая, RF, инфракрасная и другие беспроводные среды и т.д. В контекст компьютерного носителя также должна быть включена комбинация любых из упомянутых выше средств.
Система 1500 также может содержать соединение(я) 1512 связи, которое обеспечивает возможность осуществления связи устройства с другими устройствами. Дополнительно для ввода содержимого в ячейки электронной таблицы 400 согласно варианту осуществления изобретения система 1500 может содержать устройство(а) 1514 ввода данных 1514, такое как клавиатура, мышь, перо, устройство ввода речевых данных, сенсорное устройство ввода данных и т.д. Также может содержаться устройство(а) 1516 вывода данных, такое как дисплей, динамики, принтер и т.д., причем такие устройства могут использоваться для отображения электронной таблицы 400 пользователю, согласно вариантам осуществления настоящего изобретения. Все эти устройства известны и здесь не требуется их подробное описание.
Выше были описаны согласно чертежам варианты осуществления настоящего раскрытия, при этом должно быть ясно, что в настоящее изобретение могут быть внесены многочисленные изменения, которые понятны специалистам в данной области техники и которые попадают в контекст и не выходят из области раскрытого изобретения, которое определено приложенной формулой изобретения. Действительно, хотя для целей этого раскрытия был описан вариант осуществления, предпочтительный в текущее время, могут быть внесены различные изменения и модификации, которые входят в контекст настоящего изобретения.
Подобным образом, хотя в раскрытии была использована терминология, определенная для структурных признаков, методологических действий и для компьютерочитаемого носителя, содержащего такие действия, должно быть понято, что предмет, определенный в приложенной формуле изобретения, не обязательно ограничен определенной структурой, действиями, признаками или средствами, которые здесь описаны. Скорее, определенные признаки и действия, описанные выше, раскрыты в виде примерных видов реализации формулы изобретения. Например, хотя в некоторых примерных вариантах осуществления были проиллюстрированы и описаны два механизма повторного вычисления, может использоваться любое количество "N" процессоров и соответственно механизмов повторного вычисления. Для специалистов очевидны другие варианты осуществления или усовершенствования, которые входят в контекст и область настоящего изобретения. Следовательно, конкретные структуры, действия или средства раскрыты как возможные варианты осуществления для реализации заявленного изобретения. Изобретение определяется приложенной формулой изобретения.
1. Компьютерно-реализуемый способ функционирования приложения электронных таблиц с использованием множества процессоров, содержащий этапы, на которых:
определяют количество процессоров;
выделяют средство повторного вычисления для каждого процессора;
поддерживают поток управления для синхронизации обработки средств повторного вычисления;
упорядочивают формулы в единую последовательность вычислений;
пытаются оценить первую формулу в единой последовательности вычислений с помощью первого средства повторного вычисления;
если первая формула является зависимой от первой вспомогательной формулы, перемещают первую зависимую формулу и первую вспомогательную формулу в очередь для первого средства повторного вычисления;
пытаются оценить вторую формулу в единой последовательности вычислений с помощью второго средства повторного вычисления;
если вторая формула является зависимой от второй вспомогательной формулы, перемещают вторую зависимую формулу и вторую вспомогательную формулу в очередь для второго средства повторного вычисления;
продолжают выполнение итерации вниз по единой последовательности вычислений до достижения конца последовательности; и
упорядочивают, посредством потока управления, очереди для первого и второго средств повторного вычисления на основе отношений "зависимая/вспомогательная", при этом первую зависимую формулу делают дочерней для первой вспомогательной формулы и вторую зависимую формулу делают дочерней для второй вспомогательной формулы.
2. Компьютерно-реализуемый способ по п.1, в котором вторая вспомогательная формула сама является дочерней для третьей вспомогательной формулы.
3. Компьютерно-реализуемый способ по п.1, дополнительно содержащий этапы, на которых:
если первая формула является зависимой от первой вспомогательной формулы, маркируют первую зависимую формулу для ее отслеживания;
определяют, является ли первая вспомогательная формула зависимой от первой зависимой формулы;
если первая вспомогательная формула является зависимой от первой зависимой формулы, маркируют первую вспомогательную формулу для ее отслеживания;
извлекают отслеженные формулы после окончания итераций по единой последовательности вычислений;
определяют, является ли какая-либо из отслеживаемых формул "грязной";
если какая-либо из отслеживаемых формул является "грязной", перемещают отслеживаемую формулу и ее дочернюю или дочерние формулы в одноуровневую последовательность вычислений без каких-либо дочерних последовательностей или уровней зависимости; и
вычисляют одноуровневую последовательность вычислений с использованием одного потока.
4. Компьютерно-реализуемый способ по п.1, дополнительно содержащий этапы, на которых:
определяют, является ли первая зависимая формула зависимой от невычисленной второй вспомогательной формулы; и
если первая зависимая формула является зависимой от первой вспомогательной формулы и является зависимой от невычисленной второй вспомогательной формулы, перемещают первую зависимую формулу на отдельный уровень зависимости.
5. Компьютерно-реализуемый способ по п.1, дополнительно содержащий этапы, на которых:
определяют, имеет ли первая вспомогательная формула и первую зависимую формулу, и вторую зависимую формулу; и
если первая вспомогательная формула имеет и первую зависимую формулу, и вторую зависимую формулу, перемещают первую и вторую зависимые формулы на отдельный уровень зависимости.
6. Компьютерно-реализуемый способ по п.1, дополнительно содержащий этапы, на которых:
определяют, существуют ли в последовательности вычислений формулы, которые должны быть выполнены только потоком управления; и
перемещают формулы только потока управления на отдельный уровень зависимости.
7. Компьютерно-реализуемый способ по п.1, в котором формулу только потока управления перемещают на уровень зависимости, непосредственно следующий за текущим уровнем зависимости.
8. Компьютерно-реализуемый способ по п.1, в котором операции потока первого средства повторного вычисления приостанавливают при достижении потоком конца уровня зависимости.
9. Компьютерно-реализуемый способ по п.1, в котором операции потока первого средства повторного вычисления приостанавливают при заполнении очереди первого средства повторного вычисления.
10. Компьютерно-реализуемый способ по п.1, в котором формулу только потока управления помещают в очередь для таких формул.
11. Машиночитаемый носитель, на котором сохранены машиноисполняемые команды, которыми при их исполнении компьютером осуществляется способ функционирования приложения электронных таблиц с использованием множества процессоров, содержащий этапы, на которых:
определяют количество процессоров;
выделяют средство повторного вычисления для каждого процессора;
поддерживают поток управления для синхронизации обработки средств повторного вычисления;
упорядочивают формулы в единую последовательность вычислений;
пытаются оценить первую формулу в единой последовательности вычислений с помощью первого средства повторного вычисления;
если первая формула является зависимой от первой вспомогательной формулы, перемещают первую зависимую формулу и первую вспомогательную формулу в очередь для первого средства повторного вычисления;
пытаются оценить вторую формулу в единой последовательности вычислений с помощью второго средства повторного вычисления;
если вторая формула является зависимой от второй вспомогательной формулы, перемещают вторую зависимую формулу и вторую вспомогательную формулу в очередь для второго средства повторного вычисления;
продолжают выполнение итерации вниз по единой последовательности вычислений до достижения конца последовательности; и
упорядочивают, посредством потока управления, очереди для первого и второго средств повторного вычисления на основе отношений "зависимая/вспомогательная", при этом первую зависимую формулу делают дочерней для первой вспомогательной формулы и вторую зависимую формулу делают дочерней для второй вспомогательной формулы.
12. Машиночитаемый носитель по п.11, при этом вторая вспомогательная формула сама является дочерней для третьей вспомогательной формулы.
13. Машиночитаемый носитель по п.11, при этом способ дополнительно содержит этапы, на которых:
если первая формула является зависимой от первой вспомогательной формулы, маркируют первую зависимую формулу для ее отслеживания;
определяют, является ли первая вспомогательная формула зависимой от первой зависимой формулы;
если первая вспомогательная формула является зависимой от первой зависимой формулы, маркируют первую вспомогательную формулу для ее отслеживания;
извлекают отслеженные формулы после окончания итераций по единой последовательности вычислений;
определяют, является ли какая-либо из отслеживаемых формул "грязной";
если какая-либо из отслеживаемых формул является "грязной", перемещают отслеживаемую формулу и ее дочернюю или дочерние формулы в одноуровневую последовательность вычислений без каких-либо дочерних последовательностей или уровней зависимости; и
вычисляют одноуровневую последовательность вычислений с использованием одного потока.
14. Машиночитаемый носитель по п.11, при этом способ дополнительно содержит этапы, на которых:
определяют, является ли первая зависимая формула зависимой от невычисленной второй вспомогательной формулы; и
если первая зависимая формула является зависимой от первой вспомогательной формулы и является зависимой от невычисленной второй вспомогательной формулы, перемещают первую зависимую формулу на отдельный уровень зависимости.
15. Машиночитаемый носитель по п.11, при этом способ дополнительно содержит этапы, на которых:
определяют, имеет ли первая вспомогательная формула и первую зависимую формулу, и вторую зависимую формулу; и
если первая вспомогательная формула имеет и первую зависимую формулу, и вторую зависимую формулу, перемещают первую и вторую зависимые формулы на отдельный уровень зависимости.
16. Машиночитаемый носитель по п.11, при этом способ дополнительно содержит этапы, на которых:
определяют, существуют ли в последовательности вычислений формулы, которые должны быть выполнены только потоком управления; и
перемещают формулы только потока управления на отдельный уровень зависимости.
17. Машиночитаемый носитель по п.11, при этом формулу только потока управления перемещают на уровень зависимости, непосредственно следующий за текущим уровнем зависимости.
