CN1755633A - 用于电子表格链式计算的多线程处理的方法和系统 - Google Patents

Abstract

本发明的诸实施例涉及在电子表格程序中使用多个处理器进行链式计算的并行处理方法，其中每个处理器都具有单独的重算引擎。诸操作基本上包括首先确定多个可用处理器，然后将一个重算引擎分配给每个可用处理器，在重算引擎之间分发公式，然后，在电子表格程序中调用重算操作时，并行地对被分配给每个重算引擎的公式求值。

Description

用于电子表格链式计算的多线程处理的方法和系统

技术领域

本发明涉及电子表格计算处理，尤其涉及运行在多处理器环境中的电子表格程序的链式计算。

背景技术

传统的电子表格程序如Microsoft Excel利用单个计算链处理电子表格中公式的计算和重算，该计算链在本质上是被输入到Excel当前载入的所有工作表中的全部公式的有序列表。此外，有涉及这一计算链的每个变量的单个副本。在公式被输入到电子表格时，该公式被添加到全局计算链的开始。当通过修改公式所依赖的单元的内容或手动请求重算操作触发重算(recalc)操作时，Excel将会循环访问计算链中，并重新计算已经被标记为“脏”(即，等待重算)的任何公式。因此，单个控制线程反复访问公式的单个链。计算链和保留其排序的信息一起被保存到文件中。然后，在重新载入电子表格和计算链之后，为处理公式，诸公式根据其依存关系以合适的顺序排列。这就防止了Excel必须重复对计算链进行排序的工作。

下列方案例示传统的电子表格程序链式计算例程如何处理公式之间的依存关系。考虑在图15中示出的电子表格10。电子表格10的计算链12可以表示为图16。在这一传统的电子表格链12中，代码总是对最左边的第一个单元求值。在上面的情况中，代码从对第一个单元C4求值开始。在尝试对公式“＝A4+B4”求值时，计算代码发现，该公式依赖于单元A4，并且单元A4是“脏的”，即是说仍然要计算。在这一情况中，公式“＝A4+B4”称为“依赖”公式，单元A4中的公式称为“支持”公式。代码停止对公式＝A4+B4求值，将单元A4的公式压入计算链，并将其再次插入到紧靠在单元A4的公式之前。然后，计算代码从单元A4的公式开始，重新开始其工作。毫无问题，计算代码对A4求值，转移到C4。在尝试对公式＝A4+B4求值时(第二次)，计算代码得知A4现在已经被计算(不再“脏”)，但发现公式也依赖于单元B4，并且B4也是脏的。这样，代码再次停止对该公式求值，并将B4的公式移到紧靠在C4的公式之前。然后，毫无问题，代码对B4求值，并转移到C4(现在是第三次)。现在可以对C4求值，完成该过程。重新排序的链14在图17中示出。

然后保存这一重新排序的链14，用于随后的重算操作，以便电子表格程序不需要在每次电子表格中所做的改动手动或自动地请求重新计算时都重做这一分析和重新排序。对于极为复杂的电子表格需求，尤其在大型财务规划方案中，以上述方式完成长链式计算需要大量的处理时间。用户不喜欢在改变其规划中的方案时久久等待结果。因此，存在减少这一处理时间的诱因。针对这些和其他考虑提出本发明。

发明内容

根据本发明，具有在可用时利用多个处理器来处理链式计算的独特能力的电子表格程序解决上述和其他问题。

本发明的诸实施例包括处理电子表格程序中的支持和依赖公式的方法。这些操作基本上包括首先确定多个可用处理器，然后将一个重算引擎分配给每一可用处理器，在重算引擎之间分发公式，然后在电子表格程序中请求重算操作时，并行对被分发给每一重算引擎的公式求值。尤其，处理具有(例如)两个处理器的计算系统上的电子表格程序中的多个公式的方法包括以下操作：1)将第一重算引擎分配给两个处理器的其中之一，将第二重算引擎分配给两个处理器中的另一个，2)将每一公式分发给第一和第二重算引擎中的每一个，以及3)在第一和第二重算引擎中的每一个中，确定第一/下一公式是否依赖公式，如果该第一/下一公式不是依赖公式，就对第一/下一公式求值，或者，如果第一/下一公式是依赖公式，就确定支持公式的位置，以及4)如果该支持公式在同一重算引擎中，就将该支持公式移到第一/下一公式之前，并对该支持公式求值。如果该支持公式不在同一重算引擎中，就用包含该支持公式的引擎作出接收和处理依赖公式的安排。

本发明可以实现为计算机程序、计算系统或产品，如计算机程序产品。计算机程序产品可以是一种计算机存储介质，该计算机存储介质是计算机系统可读的，并且编码计算机程序的用于执行计算机进程的指令。计算机程序产品也可以是载波上的传播信号，该载波上的传播信号是计算系统可读的，并且编码计算机程序的用于执行计算机进程的指令。

通过参照下面简要叙述的附图、下面对本发明的目前优选实施例的详细描述以及所附权利要求书，可以获得对本发明及其改进的较完整的理解。

附图说明

图1例示一个根据本发明一实施例的示例性模块化软件系统。

图2例示根据本发明一实施例的软件在启动后所完成的初始操作。

图3是一个当电子表格中的单元值被修改时本发明一实施例的软件中执行的一般全部操作的方框图。

图4示出一个可以根据本发明的特定方面使用的计算机系统。

图5是一个例示用于根据本发明的特定实施例对链重算中的公式求值的基本操作的方框图。

图6是一个根据本发明一实施例的多线程重算引擎中的操作的详细流程图。

图7是一个例示用于处理图6的重算引擎中的附加链上的公式的操作的流程图。

图8是一个示出多个公式的示例性的3x3电子表格。

图9将图8中示出的单元例示为被初始载入到根据本发明一实施例运行的两个重算引擎。

图10例示图9中示出的重算引擎1和2中的公式处理。

图11将图8中示出的单元例示为被初始载入到根据本发明一实施例运行的两个重算引擎。

图12例示图11中示出的重算引擎1和2中的公式处理。

图13将图8中示出的单元的进一步例子例示为被初始载入到根据本发明一实施例运行的两个重算引擎。

图14例示图13中示出的重算引擎1和2中的公式处理。

图15是一个示例性传统电子表格。

图16是图15中示出的电子表格的计算链的表示。

图17是图15中示出的电子表格的重新排序的计算链的表示。

具体实施方式

现在将参照示出本发明诸实施例的附图，在下文中更完全地描述本发明。然而，本发明可以具体化为许多种不同形式，并且不应该被解释为限制在此所陈述的诸实施例；相反，提供这些实施例是为了使这一公开全面和完整，并向那些本领域中的技术人员完全地告知本发明的范围。

一般地，本发明涉及处理电子表格重算，尤其涉及在多于一个的处理器或处理引擎可用时以多个并行线程处理链式计算。现在参见图1，根据本发明一实施例，在逻辑上例示用于电子表格程序的功能组件模块。基本上，系统100包括处理模块102(处理模块包括操作系统中N个可用处理器，其中每个可用处理器都有一重算引擎104在其上运行)、数据库106、可用于接收和传输来自数据库106的数据并与负载控制模块110进行通信的I/O或发送/接收模块108。负载控制模块与边界检测模块112进行通信，其中边界检测模块112确定从发送/接收模块108接收到重算命令时必须重新计算的脏单元的界限和范围。

图2和3例示图1中示出的系统100所执行的基本操作。首先，在根据本发明的电子表格应用程序第一次被载入或调用时，执行操作的初始化序列200。在程序最初被载入时，例如在计算机系统410上，序列200从载入应用程序操作202开始。这一操作设置程序操作的初始信息。然后，控制转移到操作204。在操作204中，确定计算机系统410的可用处理器的数目。依赖于计算机系统410的环境，这些可用处理器可以是独立的处理器或单个芯片上的一个或多个的嵌入式协处理器，正如下面所讨论的那样。然后，控制转移到操作206。

在操作206中，可用处理器的数目和它们的存取位置被存储在数据库106中，用于将来的检索和使用。然后，在操作208中，控制返回，等候用户所指定的、关于特定电子表格的载入和处理的指令。

在运行在系统100上的任何电子表格中，当发出人工或自动的计算或重算请求以处理电子表格中的链式计算时，执行图3中所示出的操作300。首先，在操作302中，发送/检索模块108接收重算请求，正如请求所要求那样，在数据库106中检索数据。操作302可以由用户的人工请求触发以重算所显示的电子表格，或者，由来自调用例程的请求自动地触发，或者，当用户改变包含公式的电子表格的单元的值时自动地触发，或者，当用户将另一公式加入电子表格时自动地触发。

无论如何，在操作302中识别重算请求。然后，控制转移到操作304。

在操作304中，确定重算请求的作用领域和范围。这可以仅仅包括一个单元或一个依赖或支持所改变的单元内容的单元阵列。这些单元被称为“脏”单元。然后，控制转移到操作306，在操作306中，根据本发明执行重算方法。在重算完成时，控制转移到返回操作308，其中操作308将操作返回给调用代码或用户界面。

根据本发明诸实施例的方法基本上包括在电子表格应用程序启动后确定可用处理器的数目，将诸单元及其公式分发给可用处理器，然后每当重算请求被指出时，对脏单元，手动地或自动地并行对脏公式求值以“净化”脏单元。

根据本发明的诸实施例，可以在单个独立计算机系统上执行在此所描述的方法，但是通常也可以在相互连接形成分布式计算机网络的多个计算机系统上执行。图4中示出一个用于实现本发明所考虑的电子表格计算的环境400。该环境400具有一个被认为是主计算机系统的计算机系统410。如在此所使用的那样，“计算机系统”将被广泛地解释并被定义为“执行用于显示和处理文本、图形、符号、音频、视频和/或数字的程序的一个或多个设备或机器”。

本发明可用于众多其他通用或专用计算系统环境或配置。可适用于本发明的众所周知的计算系统、环境和/或配置的例子包括但不限于个人计算机、服务器计算机、手持设备或便携式设备、平板型设备、多处理器系统、基于微处理器的系统、置顶盒、可编程的消费电子设备、网络PC、小型计算机、大型计算机、包括以上任何系统或设备的分布式计算环境等等。

本发明可以在由计算机执行的计算机可执行指令的一般上下文中描述，例如程序模块。一般地，程序模块包括执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件、数据结构等等。也可以在分布式计算环境中实践本发明，在这些分布式计算环境中，由通过通信网络而被连接的远程处理设备来执行任务。在分布式计算环境中，程序模块可以位于包括存储设备在内的本地和远程计算机存储介质中。

参照图4，实施本发明的示例性系统包括以计算机410形式的通用计算设备。计算机410的诸组件可以包括但不限于处理单元420、系统存储器430和系统总线421，其中系统总线420将包括系统存储器在内的各种系统组件耦合到处理单元420。系统总线421可以是包括使用多种总线体系结构中的任一种的存储器总线或存储器控制器、外围总线以及局域总线在内的若干总线结构类型中的任一种。作为例子而非限制，此类体系结构包括工业标准体系结构(ISA)总线、微通道体系结构(MCA)总线、增强型ISA(EISA)总线、视频电子标准协会(VESA)局部总线、加速图形接口(AGP)总线以及外围组件互连(PCI)总线(也称为Mezzanine总线)。

计算机410通常包括多种计算机可读介质。计算机可读介质可以是能够被计算机410访问的任何可用介质，包括易失和非易失性介质、可移动的和不可移动的介质。作为例子而非限制，计算机可读介质可以包括计算机存储介质和通信介质。计算机存储介质包括易失性和非易失性、可移动的和不可移动的介质，该介质用存储信息如计算机可读指令、数据结构、程序模块或其他数据的任何方法或技术实现。计算机存储介质包括但不限于RAM、ROM、EEPROM、闪存或其他存储技术、CD-ROM、数字通用盘(DVD)或其他光盘存储器、磁带盒、磁带、磁盘存储器或其他磁存储设备、或者可以被用来存储所需信息并能被计算机410访问的任何其他介质。通讯介质通常以调制数据信号(如载波或其他传输机制)的形式包括计算机可读指令、数据结构、程序模块或其他数据，并包括任何信息传输介质。术语“调制数据信号”是指以在该信号中编码信息的方式来设置或改变其一个或多个特性的信号。作为例子而非限制，通信介质包括有线介质如有线网络或者直接有线连接，以及无线介质如声音、射频、红外和其他无线介质。上述任何组合也应该被包括在计算机可读介质的范围内。

系统存储器430包括易失性和/或非易失性存储器如只读存储器(ROM)431和随机存取存储器(RAM)432形式的计算机存储介质。基本输入/输出系统433(BIOS)通常被存储在ROM 431中，该基本输入/输出系统包含帮助在计算机410内的各个元件之间传输信息的基本例程，例如，在启动过程中。RAM 432通常包含处理单元420可立即访问和/或目前正在操作的数据和/或程序模块。作为例子而非限制，图4例示了操作系统434、应用程序435、其他程序模块436以及程序数据437。

计算机410也可以包括其他可移动的/不可移动的、易失性/非易失性计算机存储介质。仅仅作为例子，图4例示了从不可移动的非易失性磁介质读取或向其中写入的硬盘驱动器441、从可移动的非易失性磁盘451读取或向其中写入的磁盘驱动器452、以及从可移动的非易失性光盘456(例如，CD ROM或其他光学介质)读取或向其中写入的光盘驱动器455。可以在该示例性操作环境中使用的其他可移动的/不可移动的、易失性/非易失性计算机存储介质包括但不限于，磁带盒、闪存卡、数字通用光盘、数字视频带、固态RAM、固态ROM等等。硬盘驱动器441通常通过不可移动存储器接口如接口440连接到系统总线421，而磁盘驱动器451和光盘驱动器455通过可移动存储器接口如接口450连接到系统总线421。

以上所讨论的和图4中所例示的这些驱动器及其关联的计算机存储介质为计算机410提供计算机可读指令、数据结构、程序模块和其他数据的存储。例如，在图4中，硬盘驱动器441被例示为储存操作系统444、应用程序445、其他程序模块446和程序数据447。注意，这些组件可以等同于或不同于操作系统434、应用程序435、其他程序模块436和程序数据437。这里对操作系统444、应用程序445、其他程序模块446和程序数据447给予不同的标号来说明至少它们是不同的拷贝。用户可以通过输入设备如书写板(电子数字转换器)464、话筒463、键盘462)和定位设备461(通常指鼠标、跟踪球或触摸板)向计算机410输入命令和信息。其他输入设备(未示出)可以包括操纵杆、游戏垫、圆盘式卫星天线、扫描仪等等。这些和其他输入设备往往通过被耦合到系统总线的用户输入接口460连接到处理单元420，但也可以通过其他接口和总线结构如并行端口、游戏端口或通用串行总线(USB)连接。监视器491或其他类型的显示设备也通过接口如视频接口490连接到系统总线421。监视器491也可以与触摸屏面板493等集成，其中触摸屏面板493通过一个接口(例如，触摸屏接口492)将数字化输入(例如，笔迹)输入到计算机系统410。注意，监视器和/或触摸屏面板可以在物理上耦合到一个外壳，该外壳中计算装置410被集成到(例如)平板型个人计算机中，其中触摸屏面板493实质上充当书写板464。另外，计算机如计算设备410还可以包括其他外围输出设备，例如，可通过输出外围接口494等连接的扬声器495和打印机496。

计算机410可以运行在使用到一台或多台远程计算机如远程计算机480的逻辑连接的网络化环境中。虽然在图4中仅仅示出了存储设备481，但是远程计算机480可以是个人计算机、服务器、路由器、网络PC、对等设备或其他公共网络节点，并通常包括上文所述与计算机410相关的许多或所有元件。图4所描述的逻辑连接包括局域网(LAN)471以及广域网(WAN)473，但是也可以包括其他网络。这类网络环境常见于办公室、企业范围内的计算机网络、企业内部互联网和因特网。

当用于LAN网络环境时，计算机410通过网络接口或适配器470连接到局域网471。当用于WAN网络环境中，计算机410通常包括调制解调器472或用于在WAN 473(例如，因特网)上建立通信的其他装置。可以内置或者外置的调制解调器472可通过用户输入接口460或者其他适当的装置被连接到系统总线421。在网络化环境中，相对于计算机410描述的程序模块或它们的部分可以被存储在远程存储设备中。作为例子而非限制，图4将远程应用程序485例示为驻留在存储设备481上。应该明白，所示网络连接是示例性的，并且可以使用在计算机之间建立通信链路的其他方式。

记住计算环境，参照被执行以实现具体表现本发明各种实施例的过程的逻辑操作，描述本发明的诸实施例。这些逻辑操作实现为(1)运行在计算系统上的步骤或程序模块的计算机序列和/或(2)计算系统中相互连接的机器逻辑电路或电路模块。该实现是依赖于实现本发明的计算系统的性能需求的一种选择。因此，构成在此所描述的本发明的诸实施例的逻辑操作是指各种操作、结构化设备、动作或模块。本领域中的技术人员将认识到，这些操作、结构设备、动作和模块可以在软件、固件、在专用数字逻辑及其组合中实现而没有偏离所附权利要求书中所述的精神和范围。

图5是一个在接收到重算请求时发生的基本操作500的程序流程图。重算在操作502中开始。控制转移到操作504，其中操作504查询是否有任何被包括在重算请求涉及的单元中的脏公式。如果没有，控制转移到终止重算请求的结束操作506。如果有包含公式的单元，控制转移到操作508，操作508中，选择链内的第一公式。然后，控制转移到操作509。

查询操作509询问第一/下一公式是否脏公式，即是说，需要重算的公式。如果不是，控制转移回到操作508以选择下一个公式。如果操作509中的公式是脏的，控制从查询操作509转移到确定该公式是否依赖公式的查询操作510。

查询操作510询问第一/下一公式是否依赖公式，即是说，其中变量依赖于不在那个单元中出现的一个或多个变量的公式。如果不是，控制转移到操作512。如果操作510中的公式依赖于另一个公式，即是说，支持公式，控制就从操作510转移到抓取支持公式并将其置于依赖公式之前的操作514。然后，控制转到查询操作516。

查询操作516尝试立即对该支持公式求值。作为该求值的一部分，操作516询问该支持公式本身是否依赖公式。如果不是，控制就转移到对该支持公式求值然后对该依赖公式求值的操作512。然后，控制转回到操作504，其中操作504询问在要重算的链中是否有另一个公式。

在查询操作516中，如果应答为是，第一支持公式是本身就依赖公式，控制返回到操作514，其中操作514确定下一个(即第二)支持公式并将其置于第一支持公式之前。然后，控制再次转移到查询操作516。再次，查询操作516询问新的(第二)支持公式本身是否依赖公式。如果是，控制再次返回到操作514，在操作514中，下一支持公式被检索并被置于先前的支持公式之前。这个过程重复进行，直至发现再也没有支持公式是依赖公式。然后，控制从查询操作516转移到操作512，在操作512中，对第二支持公式求值，对第一支持公式求值，以及最后对依赖公式求值。然后，控制转回到操作504，重复上述过程，直至再也没有公式。然后，重算过程在操作506终止。

可用于电子表格程序的每个重算引擎104以类似于上述的方式接收并处理要处理的计算链的一部分。在操作302中接收到重算请求时，以及在操作304中确定具有依赖和/或支持公式的受影响单元的范围和领域时，数据库106通过发送/接收模块108给负载控制模块110提供单元信息。有了来自边界检测模块112的输入，负载控制模块的任务是将受影响的单元分发给用于处理的可用重算引擎104。例如，如果有两个处理器可用，就有两个重算引擎104可用，每个处理器上都有一个重算引擎。负载控制模块110在可用处理器102之间平均地分发链内的公式。选择分配哪个引擎的一种方法是随机地挑选重算引擎104，其中每个单元及其公式被分配给该重算引擎104。这可以通过与由负载控制模块随机数产生器分配给该单元的引擎相对应的每个单元给附上一个标志来实现。理论上，这样的随机放置最后会使每个重算引擎上的负载相等。或者，再分配可以是简单数字分发，即是说，第一公式到第一引擎，第二公式到第二引擎，第三公式到第三引擎，等等，然后重复这一过程直到处理器的数目被用尽。

在多处理器环境中，如在本发明的多处理器环境中，重算引擎操作组成处理变量重算的独立并行线程。由于在重算引擎中的单元载入最好是随机的，作为随机放置的结果，通常会平衡每个线程上的负载。负载控制模块也监视几个重算引擎的载入，可以在引擎之间重新分配单元。或者，负载控制模块可以偏向用户所期望的一个引擎或另一个引擎，或自动地偏向一个引擎或另一个引擎，以平衡特定链的计算需求。

借助于并行处理器操作的公式中的公式和数据的处理可能导致可使结果无效的非计划中的结果。例如，两个不同的线程可能为访问个别单元或为改变存储在公共单元中的数据而竞争。因此，在本发明的诸实施例中提供一系列规则，应用于由各种重算引擎执行的每一和所有数据操作，以避免这样的非计划中的结果。

下列软件规则应用于由每个可用重算引擎执行的求值方法。在本说明书下面进一步讨论的例子中，利用两个重算引擎，但只作为示例，以便于描述这些规则的操作。

这些一般规则是：

1.只有一个系主重算引擎可以修改其重算链中的诸项(公式及其放置)。

2.系主重算引擎和其他(诸)重算引擎可以修改重算引擎附加链上的项。

3.锁定避免了同时修改任何附加链上的项。例如，如果重算引擎1想把公式移到重算引擎2，它首先必须请求锁定重算引擎2的附加链。

4.一旦有了锁定，它就将单元的“附加”值设置为“真”，将单元的引擎值从重算引擎1设置为重算引擎2，将公式移到另一引擎重算引擎2，并解除锁定。

5.同时，重算引擎2可能想要将单元公式压入其自己的重算引擎的附加链。然而，如果其重算引擎的附加链被锁定，就必须等待，直到解锁之后才能进行这样的移动。

图6是一个在本发明的一个示例性实施例中由每个重算引擎执行的操作的详细流程图600。应该明白，诸单个操作的序列可以改变。下列描述仅属于一个实施例。这类改变对本领域中的技术人员来说是显而易见的，在此集成所有这类改变。

操作在操作602开始。这里初始化每个重算引擎104并开始接收公式。当负载控制模块110向重算操作的公式已经被全部分发的重算引擎发信号时，控制转移到操作604。

在操作604中，重算引擎104的第一公式被标记为需要求值。控制转移到询问公式是否依赖公式的操作605。如果只有常数或在公式中先前确定的或引用的变量，控制就被转移到操作626，然后仅对该公式求值，然后以同样方式对序列中的下一公式求值，直到重算引擎的链中所有公式都被求值。然而，如果遇到的公式中的任一个是依赖公式，即是说，它是被称为支持公式的另一脏公式，就停止求值，控制转移到查询操作606。

查询操作606询问支持公式是否位于同一重算引擎或另一重算引擎上。如果发现正在检查的依赖公式中的支持公式在同一重算引擎上，控制就转移到查询操作608。如果正在检查的依赖公式的支持公式不在同一重算引擎上，控制就转移到操作610。

在操作610中，将锁定请求发送给支持公式所驻留的重算引擎，并且，在建立锁定请求后，控制转移到查询操作612。查询操作612确定包含支持公式的重算引擎是否正在处理或已经完成其计算。如果支持重算引擎空闲，在接收到锁定请求之前已经完成其计算并向操作610发出锁定，就释放锁定，并且控制转移回操作604以重试该依赖公式的求值。另一方面，如果支持重算引擎正忙于计算，对查询操作612的应答就为“否”，控制转移到操作616。

在操作616中，从重算引擎移动依赖公式，置于附加到支持重算引擎的正规计算链的附加链上。然后，控制转移到操作618，在操作618中释放对重算引擎的锁定。然后，控制转移到查询操作620。

在查询操作620中，询问需要求值的初始重算引擎在其正规计算链中是否还有公式这一问题。如果应答为“是”，控制就转移回到调查和对正规计算链的下一公式求值的操作604。另一方面，如果在初始重算引擎的正规链中不再有需要求值的公式，控制就转移到用于对初始重算引擎的附加链求值的例程700，如图7所示。因此，控制将会转移到操作702，在操作702中，请求并获得用于重算引擎自己的附加链的锁定。这就保证在锁定有效时，重算引擎自己的附加链上的值或公式不会被修改。一旦获得锁定，控制就转移到查询操作704。

在查询操作704中，查询在附加链上是否有任何公式。如果在附加链上有公式，控制转移就到操作706。操作706将所有公式从重算引擎的附加链移除，并将它们按顺序置于该引擎的正规链上。然后，控制转移到操作708，在操作708中释放自锁。然后，控制转到操作710。

在操作710中，对于当前在正规链上的公式，在604中重新开始重算。如上所述，公式的求值从附加链取出的第一公式开始，顺序地处理正规链上的所有公式，直到所有公式都已经被求值。

如果查询操作704的应答为“否”，在引擎的附加外链上就没有公式，然后控制就转到操作714。这里，重算引擎标注自己已经完成计算，并且，控制转移到释放重算引擎上的自锁的操作716。然后控制转到操作712，其中操作712提供该重算引擎的计算和求值已经完成的状态。一旦所有重算引擎都提供计算和求值已经完成的状态，整体上而言重算就完成了。

返回查询操作606，如果确认重算引擎中的第一公式有支持公式，并且该支持公式实质上在同一重算引擎中，控制就转移到查询操作608。在查询操作608中，询问支持公式是否在重算引擎的正规(即是说，常规)链上这一问题，或者如果不在，它就是在重算引擎的附加链上。如果该支持公式在重算引擎的正规链上，控制就转移到操作622。这里，该支持公式仅仅从其在链中的位置被移到紧靠在依赖公式之前，并立即被求值。然后，控制转到查询操作624。

在查询操作624中，首先检查该支持公式，并确定它本身是否依赖公式。如果它是依赖公式，控制就返回到查询操作606，以调查该支持公式的支持公式。如前所述，操作流程从操作606继续。

另一方面，如果查询操作624的应答为“否”，该支持公式就不是依赖公式，控制就转到直接对公式求值的操作626。紧接着操作626中的求值，控制再次转到询问重算引擎的正规链上是否有公式的查询操作620。如果在正规链上没有剩余的公式，控制就转到操作例程700，正如上面所讨论的那样。如果重算引擎的正规链上有另外的公式，控制就返回到对正规链中的下一公式求值的操作604。

如果查询操作608的应答为“否”，该支持公式就不在重算引擎的正规链上，于是它一定是在该引擎的附加链上。因此，控制转到发出自锁请求的操作628。在建立自锁后，控制转到操作630。在操作630中，从附加链移除支持公式。然后，控制转移到操作632。在操作632中，刚才被移除的支持公式被置于重算引擎的正规链中，紧靠在调用依赖公式之前。然后，控制转移到操作634。如上所述，在操作634中，释放自锁，控制转移到查询操作624。

图8中所示出的如何在简单3x3电子表格800上执行这一过程的几个例子在图9至图14中例示。

图9和图10例示第一例子，在该例子中，根据上面所描述的本发明的方法处理图8中所示出的示例性电子表格程序800的公式。图11和图12例示使用图8中所示出的公式的不同载入的相同方法的第二例子。图13和图14例示使用图8中所示出的相同公式的另一不同载入的第三个例子。

在对任何公式求值之前，作为随机分布载入图8的电子表格程序中的公式的结果，在具有两个处理器的系统900上的工作的电子表格程序中，将公式载入两个引擎——重算引擎1和2，图9例示该示例性的载入，其中重算引擎1和2分别被指出为引擎902和904。此时，引擎902和904中的每一个都有公式的正规链和空的附加链。重算引擎1持有单元A1、B1和B2中的公式。单元A2、A3和C2中的常数不是被载入到重算引擎1中，而是在处理过程中可以用于重算引擎1和重算引擎2的求值。此时，重算引擎2持有单元B3、C1和C3中的公式。

正如所例示的那样，从图9和图10中的左边开始，向右边进行下去，对每个引擎中的每个项或单元公式求值。此外，在每个引擎中独立地、并行地和顺序地进行求值。

首先，重算引擎1尝试对项A1，公式＝4*B3求值。然而，单元B3中的公式不在重算引擎1中，并且还没有被求值。由于B3是在重算引擎2中，重算引擎1获得对引擎2的附加链的锁定，项A1被移到重算引擎2的附加链。这由例示这一移动的箭头908在图10中示出。然后，移除该锁定。然后，引擎1中的控制转移为对下一项，单元B1求值。单元B1包含公式“＝A1*C3”。项A1还没有被求值，现在驻留在重算引擎2上。因此，再次向重算引擎2的附加链发出锁定请求，当锁定请求被接收到并且锁定被建立时，项B1被移到重算引擎2的附加链，并被置于项A1之后。这由箭头908在图10中示出。

然后，引擎1中的控制转移为对下一项，单元B2求值。单元B2包含公式“＝3*B1”。项B1还没有被求值，现在驻留在重算引擎2。因此，再次向重算引擎2的附加链发出锁定请求，当锁定请求被接收到并且锁定被建立时，项B2被移到重算引擎2的附加链，并被置于项B1之后。这由箭头910在图10中示出。

与重算引擎1的上述第一个操作并行，重算引擎2开始对项B3，公式“＝A3*4”求值。项B3包含A3，A3是常数2，因此不是依赖公式。因此，立即完成计算，引擎2接着对C1中的公式求值。单元C1包含公式“＝A1+B1+C2”。这个公式是依赖公式。因此，引擎2确定A1的支持公式位于何处。它在引擎2的附加链上。因此，发出自锁请求，在建立自锁后，如箭头912所示，立即将该公式从附加链移到紧靠在单元C1的公式之前。由于单元A1的公式不再在引擎2的附加链上，它的中间位置由虚线矩形指出。然后，所述引擎2对公式＝4*B3求值，而后移回到公式＝A1+B1+C2。引擎2在单元B1中的公式停机。这个公式是在重算引擎2的附加链上被发现的支持公式。因此，再次发出自锁请求，在建立自锁后，如箭头914所示，公式＝A1*C3被移到在单元C1的公式之前的正规链。引擎2对B1的公式求值，得知尽管已经计算A1，C3仍是需要计算的支持公式。因此，发出自锁请求，在建立自锁后，C3的公式被移到正规链，就在B1之前。现在引擎2对C3中的公式求值。然后，立即计算C3中的公式。因为现在已经计算A1和C3，所以下一步引擎2立即计算B1中的公式。现在，已经知道公式＝A1+B1+C2的所有元素，于是对单元C1中的公式求值。这就完成了重算引擎2的正规链的处理。

然后，引擎2转移为查看其附加链。附加链包含单元B2中的公式＝3*B1。在重算引擎2链上建立自锁，并将这个公式从附加链移到重算引擎2的正规链。没有用箭头指出正规链的重算，因为这只会使复杂的图变得复杂。因为得知现在已经计算单元B1中的公式，所以立即对单元B1中的公式求值，完成计算。引擎2得知，在其正规和附加链上已经没有计算，因此将其本身设置为已经完成的状态。

引擎1得知，在其正规和附加链上已经没有计算，因此将其本身设置为已经完成的状态。

这就完成了重算引擎1和2的处理。

在对任何公式求值之前，作为随机分布的载入图8中的电子表格中的公式的结果，在系统1100的处理器1102和1104上的操作中，发生不同的示范性的将公式载入到重算引擎1和2中，图11和图12例示发生该载入的第二例子。重算引擎持有单元A1、C1、和C3中的公式。单元A2、A3和C2中的常数不是被载入到重算引擎1，而是在处理过程中可以用于重算引擎1和重算引擎2的求值。此时，重算引擎2持有单元B1、B3和B2中的公式。

正如所例示的那样，从图11和图12中的左边开始，向右边进行下去，对每个引擎中的每个项或单元公式求值。此外，在每个引擎中并行地和顺序地完成求值。

首先，重算引擎1尝试对项A1，公式＝4*B3求值。然而，单元B3中的公式不在重算引擎1中，并且还没有被求值。由于B3是在重算引擎2中，重算引擎1获得对引擎2的附加链的锁定，项A1被移到重算引擎2的附加链，如箭头1202所示。移除锁定。然后，引擎1的控制转移为对下一项求值，单元C1中的公式。单元C1包含公式＝A1+B1+C2。项A1还没有被求值，现在驻留在重算引擎2。因此，再次向重算引擎2的附加链发出锁定请求，当锁定请求被接收到时，项C1被移到重算引擎2的附加链，并被置于项A1之后，如箭头1204所示。

与重算引擎1的上述第一个操作并行，重算引擎2尝试对项B1，公式＝A1*C3求值。然而，项B1包含A1。于是软件确定A1是在重算引擎2上还是在重算引擎1上。由于重算引擎1并行工作，此时A1可能是在重算引擎1上。因此，如箭头1206所示，在首先获得对重算引擎1的附加链的锁定之后，项B1被移到重算引擎1的附加链。在转移之后，移除锁定。然后，重算引擎2中的控制转移为对单元B3中的公式求值。单元B3有公式＝A3*4。由于单元A3包含常数2，单元B3中的公式不是依赖公式，并因此立即确定其值为“8”，然后，控制切换为对单元B2中的公式求值。同时，有可能正在将单元C1中的公式从重算引擎1转移到重算引擎2的附加链。单元B2中的公式是“＝3*B1”。单元B1中的公式被转移到重算引擎1的附加链。结果，正如箭头1208所指出的那样，现在单元B2中的公式也被转移到重算引擎1中的附加链。

然后，重算引擎2锁定其本身，并将当前在其附加链上的所有公式移到其正规链进行处理(为简单起见，在图12中未示出)。现在，要计算的下一个公式在A1中(＝4*B3)。由于B3先前已经被求值为“8”，它已经被“净化”。因此，项A1立即被求值，变成“32”。

在重算引擎2计算B3的同时，重算引擎1对单元C3中的公式求值。这一依赖公式是＝B3*A3。B3是支持公式。可能已经完成B3的求值，因此可以立即对该公式求值。但如果还没有完成B3的求值，单元C3中的公式就会被转移到重算引擎2的附加链，如虚线箭头1210所示。读者应该理解，这样的转移完全取决于两个引擎之间所涉及的处理时间。

继续重算引擎2，由于已经计算项B3和项A1，尝试对下一个公式C1求值。单元C1中的公式是依赖公式，依赖于支持公式B1和常数C2以及所求值的项A1。项B1现在在重算引擎1的附加链中。在重算引擎1中，驻留于附加链的单元B1和B2中的两个公式，有可能已经被移到正规链，并且计算已经开始(简单起见，未在图中示出)。如果已经计算单元B1中的公式，就立即计算单元C1中的公式。如果还没有计算单元B1中的公式，就请求锁定重算引擎1的附加链，单元C1中的公式将被移回到重算引擎1的附加链，等候处理。为简单起见，该操作没有用箭头示出。然后，重算引擎2中的控制再次继续对单元C3中的公式求值。此时已经计算B3，A3是常数，因此立即计算单元C3中的公式。重算引擎2得知，在其正规和附加链上没有计算，因此将其本身设置为已经完成的状态。这就完成重算引擎2中的操作。

最后返回重算引擎1，请求自锁，将附加链中的公式移到正规链，释放自锁被，并对公式求值。一旦已经确定单元A1中的公式和单元C3中的公式，就立即计算单元B1中的公式＝A1*C3。然后控制移到单元B2中的公式。一旦刚才已经确定单元B1中的值，就立即计算单元B中2的公式的值。重算引擎1得知，在其正规和附加链上已经没有计算，因此将其本身设置为已经完成的状态。这就完成了重算引擎1中的操作。这就完成了这个例子中的操作。

图13和图14例示第三例子，在该第三例子中，根据上面所描述的本发明的方法处理图8中所示出的示范性电子表格的公式。在对任何公式求值之前，作为随机分布的载入图8中的电子表格中的公式的结果，将公式载入1300到重算引擎1和2中，图13例示该示范性的载入。处理器1302上的重算引擎1持有单元A1、C1、B2和C3中的公式。单元A2、A3和C2中的常数不是被载入到重算引擎1，而是在处理过程中可以用于重算引擎1和重算引擎2的求值。此时，处理器1304上的重算引擎2持有单元B1和B3中的公式。

正如所例示的那样，从图13和图14中的左边开始，向右边进行下去，对每个引擎中的每个项或单元公式求值。此外，在每个引擎中并行地和顺序地完成求值。

首先，重算引擎1尝试对项A1，公式＝4*B3求值。然而，单元B3中的公式不在重算引擎1中，并且还没有被求值。由于B3是在重算引擎2中，重算引擎1获得对引擎2的附加链的锁定，项A1被移到重算引擎2的附加链，如箭头1402所示。移除锁定。然后，控制转移为对下一项，单元C1求值。单元C1包含公式＝A1+B1+C2。项A1还没有被求值，现在驻留在重算引擎2。因此，再次向重算引擎2的附加链发出锁定请求，当锁定请求被接收到时，项C1被移到重算引擎2的附加链，并被置于项A1之后，如箭头1404所示。

与重算引擎1的上述第一个操作并行，重算引擎2尝试对项B1，公式＝A1*C3求值。然而，项B1包含A1。于是软件确定A1是在重算引擎2上还是在重算引擎1上。由于重算引擎1并行工作，此时可以假设A1仍在重算引擎1上。因此，如箭头1406所示，在首先获得对重算引擎1的附加链的锁定之后，项B1被移到重算引擎1的附加链。在转移之后，移除锁定。然后，重算引擎2中的控制转移为对项B3求值。项B3有公式＝A3*4。由于单元A3包含常数2，立即对单元B3中的公式求值，重算引擎2的正规链中没有发生进一步的动作。同时，有可能正在将项C1从重算引擎1转移到重算引擎2的附加链。

重算引擎2已经完成其正规链中的所有操作。因此，然后它将附加链的公式压入正规链，并开始求值(为简单起见，图14中未示出)。然后，重算引擎2开始对第一公式，单元A1求值。单元A1的公式是＝4*B3。由于B3先前已经被求值，它已经被“净化”，现在是“8”。因此，项A1立即被求值，并变成干净的“32”。

在重算引擎2计算B3的同时，重算引擎1对单元B2中的公式求值。这一依赖公式是＝3*B1。B1是支持公式。然后程序确定单元B1中的公式是在其自身的重算引擎1上，在其附加链中，因此，它建立自锁并将单元B1中的公式移到紧靠在单元B2中的公式之前，如箭头1408所示，并尝试对单元B1中的公式求值。单元B1的公式是＝A1*C3。此时，项A1在重算引擎2的附加链上，假设没有计算A1。因此，重算引擎1获得对重算引擎2的附加链的锁定，并将单元B1中的公式转移到重算引擎2的附加链，如箭头1410所示，并且释放锁定。

在重算引擎1中，再次尝试对单元B2中的公式求值，但单元B2中的公式是依赖公式，而B1是刚被转移到重算引擎2的支持公式。因此，如箭头1412所示，重算引擎1获得锁定并将单元B2中的公式转移到重算引擎2的附加链。

同时，在重算引擎2上，一旦已经计算单元B3中的公式和单元A1中的公式，就对单元C1中的下一公式求值。单元C1中的公式是依赖公式，依赖于单元B1中的支持公式、单元C2中的常数以及单元A1中所求值的公式。现在，单元B1中的公式是在重算引擎2中，因此单元B1中的公式被移到单元C1中的公式之前，如箭头1414所指出，并立即被求值。单元B1中的公式是依赖公式，依赖于A1和C3。同时，单元A1中的公式已经被求值，但单元C3中的公式可能还没有被求值，如果是这种情况，就将其置于重算引擎1。然而，如果这时C3已经被求值，就用它的值(16)来对单元B1中的公式求值，然后对单元C1中的公式求值。另一方面，如果C3还没有被求值，就请求锁定重算引擎1的附加链，并且，当被锁定时，项B1再次被移到(虚线箭头1416)重算引擎1的附加链。

最后，在重算引擎2中，尝试对单元B2中的公式求值。B2中的公式是依赖公式，依赖于B1。因此，至此可能已经对单元B1中的公式求值，对B2求值，重算完成。在重算引擎1中，处理将随着单元C3中公式的求值的完成而完成，或者可选地，如果单元B1中的公式被再次移到重算引擎1的附加链，处理将随着单元B1中公式的求值的完成而完成。这就完成了该第三例子中的操作。

尽管已经用结构特征、方法动作和包含这类动作的计算机可读介质的特异性语言对本发明进行了描述，但应该明白，由所附权利要求书定义的本发明，并非仅仅局限于所描述的具体特征、动作或介质。作为例子，公式求值的处理不必像例子所描述的那样从左到右。不需要公式在引擎之间的物理移动。相同的效果可以通过将标志分配给所涉及的单元、仅仅改变指出要处理的公式或那些已经被处理或被“净化”的公式的标志以及指针来获得。因此，具体结构、动作或介质只是作为实现权利要求所述的本发明的优选形式而公开。

Claims (26)

1.一种处理电子表格程序中的支持和依赖公式的方法，包括：

确定多个可用处理器；

如果可用处理器的数目至少是两个，则给每个可用处理器分配一重算引擎；

在所述重算引擎之间分发公式；以及

对分配给每个重算引擎的公式求值。

2.如权利要求1所述的方法，其特征在于，所述处理是由一操作系统执行的。

3.如权利要求1所述的方法，其特征在于，所述确定操作包括在程序启动之后向计算机操作系统查询多个处理器是否是可用。

4.如权利要求1所述的方法，其特征在于，所述分发操作包括：

选择第一公式；

随机地将所述第一公式分配给所述重算引擎中随机的一个；

为每个下一公式重复所述选择和分配操作，直到所有公式都被分配给所述重算引擎之一。

5.如权利要求1所述的方法，其特征在于，所述对每个重算引擎的求值操作包括：

选择第一公式；

确定所述第一公式是依赖公式还是支持公式；

如果所述第一公式是支持公式，则对所述公式求值；

如果所述第一公式是依赖公式，则确定该依赖公式的支持公式是否在所述重算引擎中；以及

如果该依赖公式的所述支持公式是在所述重算引擎中，则将所述支持公式置于所述第一公式之前。

6.如权利要求5所述的方法，其特征在于，还包括：

确定被置于所述第一公式之前的该支持公式是否为依赖公式；

如果该支持公式不是依赖公式，则对该支持公式求值；以及

如果该支持公式是依赖公式，则确定该依赖公式的另一支持公式是否在所述重算引擎中，以及，如果是在所述重算引擎中，则将所述另一支持公式置于所述支持公式之前，并对所述另一支持公式求值。

7.如权利要求5所述的方法，其特征在于，所述求值操作还包括：

如果所述第一公式是依赖公式，而且该依赖公式的支持公式不在所述重算引擎中，则确定所述支持公式的重算引擎位置，并将所述第一公式移到所述重算引擎。

8.如权利要求5所述的方法，其特征在于，所述求值操作还包括：

如果所述第一公式是依赖公式，并且该依赖公式的支持公式不在所述重算引擎中，则确定所述支持公式的重算引擎位置，并查询有所述支持公式的重算引擎是否完成计算，以及，如果已经完成，则再次尝试对所述依赖公式求值，如果没有完成，则将所述依赖公式移到有所述支持公式的重算引擎中。

9.如权利要求8所述的方法，其特征在于，被移到有所述支持公式的重算引擎的所述依赖公式被置于所述重算引擎的附加链上。

10.一种计算机系统可读的计算机程序产品，其有形地包含可由计算机系统执行以实现权利要求1所述的方法的指令程序。

11.一种计算机系统可读的计算机程序产品，其有形地包含可由计算机系统执行以实现权利要求5所述的方法的指令程序。

12.一种处理具有两个处理器的操作计算系统上的电子表格程序中的多个公式的方法，所述方法包括：

将第一重算引擎分配给所述两个处理器之一，并将第二重算引擎分配给所述两个处理器中的另一个；

将每个公式分发给所述第一和第二重算引擎之一；

在所述第一和第二重算引擎的每一个中：

确定第一/下一公式是否为依赖公式；

如果所述第一/下一公式不是依赖公式，则对所述第一/下一公式求值；

如果所述第一/下一公式是依赖公式，则确定支持公式的位置；

如果所述支持公式是在同一重算引擎中，则将所述支持公式移到所述第一/下一公式之前；以及

对所述支持公式求值。

13.如权利要求12所述的处理方法，其特征在于，还包括：

为所述重算引擎中的下一公式重复所述确定和求值操作。

14.如权利要求12所述的处理方法，其特征在于，还包括：

确定所述支持公式是否为依赖公式；

如果所述支持公式是依赖公式，则确定其支持公式的位置；

如果其支持公式是在同一重算引擎中，则将其支持公式移到它所支持的支持公式之前；以及

对其支持公式求值，然后对所述支持公式求值。

15.如权利要求14所述的处理方法，其特征在于，还包括为在所述第一和第二重算引擎中的每个下一公式重复所述确定、求值、移动和求值操作。

16.如权利要求12所述的处理方法，其特征在于，还包括：

如果所述支持公式不是在同一重算引擎中，则将所述依赖公式移到所述第一和第二重算引擎中的另一个。

17.如权利要求12所述的处理方法，其特征在于，移动所述依赖公式包括将所述依赖公式添加到所述第一和第二重算引擎的另一个中的附加链。

18.一种处理电子表格程序中的公式链中的支持和依赖公式的系统，包括：

用于确定多个可用处理器并将一重算引擎分配给每一可用处理器的模块；

用于在所述重算引擎之间分发所述公式的负载控制模块；以及

用于并行地对被分配给每一重算引擎的所述公式求值的处理模块。

19.如权利要求1所述的系统，其特征在于，所述处理模块驻留于一操作系统中。

20.如权利要求1所述的系统，其特征在于，所述确定模块在程序启动时向计算机操作系统查询多个处理器是否可用，然后将一重算引擎分配个每一可用处理器。

21.如权利要求3所述的系统，其特征在于，所述负载控制模块可用于选择第一公式、随机地将所述第一公式分配给所述重算引擎中随机的一个、以及对每个下一公式重复所述选择和分配操作，直到所有公式都被分配给所述重算引擎。

22.一种包含计算机可执行指令的计算机可读介质，所述计算机可执行指令在被计算机执行时执行一种处理电子表格程序中的支持和依赖公式的方法，所述方法包括：

确定多个可用处理器；

如果所述可用处理器的数目是至少两个，则将一重算引擎分配给每一可用处理器；

在所述重算引擎之间分发所述公式；以及

对被分配给每一重算引擎的所述公式求值。

23.如权利要求22所述的计算机可读介质，其特征在于，所述处理方法中的确定操作包括在程序启动后向计算机操作系统查询多个处理器是否可用。

24.如权利要求22所述的计算机可读介质，其特征在于，所述处理方法中的分发操作包括：

选择第一公式；

随机地将所述第一公式分配给所述重算引擎中随机的一个；

为每个下一公式重复所述选择和分配操作，直到所有公式都被分配给所述重算引擎之一。

25.如权利要求22所述的计算机可读介质，其特征在于，所述处理方法中对每一重算引擎的求值操作包括：

选择第一公式；

确定所述第一公式是依赖公式还是支持公式；

如果所述第一公式是支持公式，则对所述公式求值；

如果所述第一公式是依赖公式，则确定该依赖公式的支持公式是否在所述重算引擎中；以及

如果该依赖公式的所述支持公式是在重算引擎中，则将所述支持公式置于所述第一公式之前。

26.一种包含计算机可执行指令的计算机可读介质，所述计算机可执行指令在被计算机执行时执行一种处理具有两个处理器的操作计算系统上的电子表格程序中的多个公式的方法，所述方法包括：

将第一重算引擎分配给所述两个处理器之一，将第二重算引擎分配给所述两个处理器中的另一个；

将每一公式分配给所述第一和第二重算引擎之一；

在所述第一和第二重算引擎的每一个中：

确定第一/下一公式是否为依赖公式；

如果所述第一/下一公式不是依赖公式，则对所述第一/下一公式求值；

如果所述第一/下一公式是依赖公式，则确定所述支持公式的位置；

如果所述支持公式是在同一重算引擎中，则将所述支持公式移到所述第一/下一公式之前；以及

对所述支持公式求值。

Images