基于Pi演算的并行编程语言

引用本文

康辉, 王家琦, 梅芳. 基于Pi演算的并行编程语言. 吉林大学学报: 工学版, 2016, 46(1): 235-241
KANG Hui, WANG Jia-qi, MEI Fang. A parallel programming language based on Pi-calculus. Journal of Jilin University Engineering and Technology Edition, 2016, 46(1): 235-241 复制到剪切板

Permissions

基于Pi演算的并行编程语言

康辉, 王家琦, 梅芳

吉林大学计算机科学与技术学院,长春 130012

梅芳(1977-),女,讲师,博士.研究方向:自主通信,策略网管.E-mail:meifang@jlu.edu.cn

作者简介:康辉(1968-),女,副教授.研究方向:Web服务与组合.E-mail:kanghui@jlu.edu.cn

基金:国家自然科学基金项目(61073164)

摘要

针对传统编程语言不能便捷高效利用多核芯片计算资源的缺点,本文提出了一种并行编程语言并定义了核心语义及其运行时环境的相关算法。该语言以Pi演算为理论基础,首先根据Pi演算的基本结构定义语言的核心句法结构,然后以Pi演算中进程间同步通信为基础定义了核心操作语义。本文给出了在并行操作语义中进程的上下文环境的定义,设计了构成运行时环境整体架构的主要数据结构及运行时环境中基于同步通信的调度算法和基于引用计数器的垃圾回收算法,根据本文定义的句法结构可以定义出高效地利用多核芯片计算资源的并行程序。

关键词: 计算机软件; Pi演算; 编程语言; 并行编程; 多核芯片

中图分类号:TP31 文献标志码:A 文章编号:1671-5497(2016)01-0235-07

A parallel programming language based on Pi-calculus

KANG Hui, WANG Jia-qi, MEI Fang

College of Computer Science and Technology,Jilin University,Changchun 130012,China

Abstract

Considering that the traditional programming language fails to use multicore processors to calculate conveniently and effectively, a parallel programming language is proposed and its core semantics and the relative algorithms of its runtime environment are defined. This language with Pi-calculus as its theoretical foundation first defines the core syntactic structure of the language based on the basic structure of Pi-calculus, and then defines the core operating semantics on the basis of synchronous communication in Pi-calculus process. This paper also defines the context of process in parallel operating semantics and designs the main data structure, which consists of overall architecture in operating and scheduling algorithms based on synchronous communication and garbage collection algorithm based on reference count. Therefore, the proposed parallel programming language is capable of using multicore processors to calculate sources easily and effectively.

Keyword: computer application; Pi-calculus; programming language; parallel programming; multicore processors

Show Figures

0 引言

随着芯片集成技术的日趋成熟, 硬件毕竟受物理极限约束, 芯片上的元件不能无限地缩小, 我们发现当前芯片的发展规律已经不再契合于摩尔定律。实际上, 早在2005年, C++标准委员会主席Herb Sutter在Dr.Dobb’ s Journal上发表《免费午餐已经结束》^[1]一文以来, 科研工作者已经认识到如果未来不能有效地以并行化的软件充分利用并行化的多核硬件资源, 计算效率将永远停滞在略高于当前的水平上。

为了满足日益增长的计算需求, 电子元件厂商给出了答案:多核芯片。多核芯片在提升计算效率的同时也对传统的顺序编程模型提出了挑战。因此多核芯片技术也对编程语言的发展产生了潜移默化的影响。传统的顺序编程模型使并行编程变得非常复杂, 无论是信号量, 还是锁的概念, 在编程逻辑上独立的并行程序时, 都表现的不错, 但是面对需要并行进程之间需要相互通信的并行程序时, 很难保证执行的正确性和效率, 都使得开发人员不堪重负。如何以一种优雅可靠的方式处理多核并行计算问题成为了衡量编程语言好坏的重要标准。传统编程语言纷纷以添加并行库的方式解决并行编程问题。然而, 这些编程语言都有其局限性, 因为它们都没有在最初设计语言时把并行化的概念放到优先的位置考虑。本文提出了一种基于Pi演算^{[2, 3, 4, 5, 6]}的并行编程语言, 并且给出其运行时环境的核心算法。

1 并行编程语言句法规则

Pi演算是一种具有移动能力的进程演算, 其具备强大的表达能力, 可以便捷地对并行现象进行建模。Pi演算也是一种通常的计算模型, 可以完整表述图灵机的计算过程^[7]。关于基本Pi演算的基本概念及相关理论在文献[8, 9]中有详细介绍, 在此不作赘述。本文中的并行编程语言的句法规则可使得运行时环境的核心算法更易于实现。

句法规则:

Definition def D(x₁, …, x_n)=P

Process P = end

| wait

| $\begin{matrix} \overset{n}{\sum_{i = 1}} \end{matrix}$ α _i, P_i

| D(v₁, …, v_n)

| P₁‖ P₂

Prefix α =tau

| c!v

| c?(x)

| new(c)

其中语言的前缀操作new(c)表示创建新的通道c, 输出操作c!v表示在通道c上输出值v, 输入操作c?(x)表示把在通道c上接收到的值绑定到变量x上, 它们和Pi演算概念的语义相同。tau前缀表示不执行任何行为的空操作。def操作是定义进程, 其他进程可以调用定义的进程执行。

进程表达式α .P+β .Q(可以有多个选择分支, 这里以两个分支为例)在标准Pi演算语义中是非确定选择操作^[10], 但在我们的基于Pi演算的并行编程语言的语义中稍有不同:其先执行左边进程的前缀, 当前缀α 是tau或new操作时, 继续执行P进程; 当前缀α 是输出操作c!v时, 当且仅当同时存在并行进程在相同通道上执行输入前缀时(如c(x).R), 才可以继续执行P进程(同时c(x).R也执行R进程, 其中x变量被绑定为v值)。当前缀α 不满足上面两种情况时, 选择操作以同样的规则执行下一个选择分支β .Q。如果选择操作所有的分支进程都不可以执行, 整个进程将阻塞(wait操作)。end操作表示执行结束, 常常被省略, 但是它对应语义上的进程执行完毕后的执行收尾工作。并行操作和调用操作的语义和Pi演算的语义相同, 分别表示多个进程并行执行和调用对象的进程执行。

2 进程上下文环境及语义规则

2.1 进程上下文环境

在句法规则中给出了并行虚拟机调度的最小单位:进程。进程上下文环境是指进程执行过程中存储的进程状态信息。为了给出并行编程语言的具体操作语义, 本节定义了进程上下文环境及给出静态计算上下文环境大小的方法。进程上下文环境也是一个进程可以在定义好的运行时环境中运行的语义保证。

定义1:编程语言中进程局部上下文环境由局部词法环境和承诺集合组成, 包含完整进程上下文环境的并行程序定义形式如下:

Δ • ([Γ ₁; δ ₁]:P₁‖ …‖ [Γ _n; δ _n]:P_n)

其中Δ 是并行程序的全局环境(new前缀动作生成全局通道名), 是所有并行进程所共享的信息; 每个进程都有自己的局部上下文环境:承诺集合Γ 和局部词法环境δ 。其中局部词法环境δ 是将值绑定到变量上。承诺表示一个进程可能执行某种操作的状态, 是支撑运行时环境进程调度算法的核心概念。并行进程间的同步通信可促使执行对应的承诺动作。承诺的具体定义如下:

(1)进程的局部上下文环境中包含输出承诺c!v:Q, 则表示此进程有执行输出前缀c!v后执行进程Q的可能性。

(2)进程的局部上下文环境中包含输入承诺c?(x):Q, 则表示此进程有执行输入前缀c?(x)后执行进程Q的可能性(接收到的值绑定到变量x上)。

当给定并行程序定义时, 可以使用词法环境大小和承诺集合大小中的公式以递归的方式静态地计算出进程局部上下文环境的词法环境大小(即自由变量数目)和承诺集合大小, 在遇到多分支的非确定选择操作时, 计算选择分支上下文环境最大的分支作为进一步计算的基础, 保证为进程上下文分配的空间满足最大的执行分支(肯定满足其他执行分支)。因此运行时环境可以在对并行程序进行编译分析时为进程静态分配进程上下文环境所需要的存储空间, 而不需要动态分配。

词法环境大小如下:

$\begin{matrix} \begin{matrix} esize (defD (x_{1}, \dots, x_{n}) = P) = esiz e_{{x_{1}, \dots, x_{n}}}^{n} (P) \\ esiz e_{V}^{n} (end) = n \\ esiz e_{v}^{n} (\sum_{i} α_{i}, P_{i}) = ma x_{i} (esiz e_{v}^{n} (α_{i}, P_{i})) \\ esiz e_{v}^{n} (E (v_{1}, \dots, v_{m})) = \max (n, esize (def E (y_{1}, \dots, y_{m}) = \\ Q)) \\ esiz e_{v}^{n} (c ? (x), P) = esiz e_{v ⋃ {x}}^{n + 1} (P) if x \notin V \\ | esiz e_{v}^{n} (P) ot h erwise \\ esiz e_{v}^{n} (new (c), P) = esiz e_{v ⋃ {c}}^{n + 1} (P) if c \notin V \\ | esiz e_{v}^{n} (P) ot h erwise \\ esiz e_{v}^{n} (α, P) = esiz e_{v}^{n} (P) if ? α! = c ? (x) and α! = new (c) \end{matrix} \end{matrix}$

承诺集合大小如下:

$\begin{matrix} \begin{matrix} csize (defD (x_{1}, \dots, x_{n}) = P) = csize (P) csize (end) = 0 \\ csize (\sum_{i} α_{i}, P_{i}) = \max (\sum_{i} csize (α_{i}), ma x_{i} (csize (P_{i}))) \\ csize (E (v_{1}, \dots, v_{m})) = csize (def E (y_{1}, \dots, y_{m}) = Q) \\ csize (c ? (x)) = 1 csize (c! v) = 1 \\ csize (α) = 0 if α! = c ? (x) and α! = c! v \end{matrix} \end{matrix}$

2.2 语义规则

本节定义出执行句法规则的每个句法单位执行时所对应的操作语义, 以及进程上下文随着每步操作语义的动态更新规则。具体定义的语义规则如下:

$\begin{matrix} \frac{Δ ∙ (A ‖ B) \to Δ' ∙ (A'‖ B)}{Δ ∙ (B ‖ A) \to Δ' ∙ (B ‖ A')} \end{matrix}$ (par)

$\begin{matrix} \frac{\emptyset}{Δ ∙ [Γ; δ] : end \to Δ ∙ \emptyset} \end{matrix}$ (end)

$\begin{matrix} \frac{\emptyset}{Δ ∙ ([Γ; δ] : (tau, P + \sum_{i} Q_{i}) ‖ B \to Δ ∙ ([\emptyset; δ] : P ‖ B))} \end{matrix}$ (step)

$\begin{matrix} \frac{\emptyset}{Δ ∙ ([Γ; δ] : (ne w (c), P + \sum_{i} Q_{i}) ‖ B) \to Δ, \bar{c} ∙ ([\emptyset; δ, c ▷ \bar{c}] : P ‖ B)} \end{matrix}$ (new)

$\begin{matrix} \frac{defD (x_{1}, \dots, x_{n}) = P}{Δ ∙ [Γ; δ] : D (v_{1}, \dots, v_{n}) ‖ B \to Δ ∙ [\emptyset; x_{1} ▷ v_{1}, \dots, x_{n} ▷ v_{n}] : P ‖ B} \end{matrix}$ (call)

$\begin{matrix} \frac{δ (c) = \bar{c}}{Δ ∙ ([Γ; δ] : (c! v, P + \sum_{i} Q_{i}) ‖ [Γ', \bar{c} ? (x) : R; δ'] : S) \to Δ ∙ ([\emptyset; δ] : P ‖ [\emptyset; δ', x ▷ \bar{v}] : R)} \end{matrix}$ (send)

$\begin{matrix} \frac{δ (c) = \bar{c} and \bar{c} ? (x) : R \notin Γ'}{Δ ∙ ([Γ; δ] : (c! v, P + \sum_{i} Q_{i}) ‖ [Γ'; δ'] : S) \to Δ ∙ ([Γ, c! v : P; δ] : (\sum_{i} Q_{i} + wait) ‖ [Γ'; δ'] : S)} \end{matrix}$ (out)

$\begin{matrix} \frac{δ (c) = \bar{c}}{Δ ∙ ([Γ; δ] : (c ? (x), P + \sum_{i} Q_{i}) ‖ [Γ', \bar{c}! v : R; δ'] : S) \to Δ ∙ ([\emptyset; δ, x ▷ \bar{v}] : P ‖ [\emptyset; δ'] : R)} \end{matrix}$ (recv)

$\begin{matrix} \frac{δ (c) = \bar{c} and \bar{c}! v : R \notin Γ'}{Δ ∙ ([Γ; δ] : (c ? (x), P + \sum_{i} Q_{i}) ‖ [Γ'; δ'] : S) \to Δ ∙ ([Γ, c ? (x) : P; δ] : (\sum_{i} Q_{i} + wait) ‖ [Γ'; δ'] : S)} \end{matrix}$ (in)

规则par表示并行进程的独立性, 表明并行执行的进程在并行操作符中的顺序不影响具体执行结果, 因此后面的其他规则都只以并行操作符中的最左进程为例进行表述。规则end表示结束动作, 它将释放结束进程的上下文环境。规则step表示tau动作是不确定选择分支的第一个分支时, 将释放进程上下文中承诺集合, 然后执行tau动作的后续进程。规则new表示在全局环境和进程上下文环境中添加新创建的通道名字, 并且把通道绑定对应的值, 然后执行new动作的后续进程, 同时释放承诺集合。规则call表示调用已经定义的进程, 调用时清空承诺集合, 参数变量绑定调用时传递的值, 然后执行具体的进程定义。

通信和同步是并行编程语言语义中最重要的一部分。规则send表示在某通道上面发送消息时, 另外一个并行的进程的上下文环境的承诺集合存在相同通道的输入承诺, 这时两个并行进程将发生同步通信, 对应的进程从阻塞状态进入就绪状态, 然后并行地准备执行各自的后续进程(输入承诺的后续进程词法环境被更新, 接收变量绑定到接收到的值)。规则out和规则send不同, 它表示发生消息时, 并不存在有相同通道上输入承诺的并行进程。这种情况下, 当前进程阻塞, 将把输出前缀及其后续进程添加到进程上下文环境中的承诺集合中, 然后选择不确定选择操作的下一个进程执行; 当所有的不确定选择的分支都阻塞时, 整个进程将阻塞(wait动作表示)。规则recv表示在某通道上面接收消息时, 另外一个并行的进程的上下文环境的承诺集合存在相同通道的输出承诺, 这时两个并行进程将发生同步通信, 对应的进程从阻塞状态进入就绪状态, 然后并行地准备执行各自的后续进程(输入承诺的后续进程词法环境被更新, 接收变量绑定到接收到的值)。规则in表示接收消息时, 并不存在有相同通道上输出承诺的并行进程。这种情况下, 当前进程阻塞, 将把输入前缀及其后续进程添加到进程上下文环境中的承诺集合中, 然后选择不确定选择操作的下一个进程执行; 当所有的不确定选择的分支都阻塞时, 整个进程将进入阻塞状态(wait动作表示)。

引理1 由上文说明的同步通信语义可知, 同一通道不能同时存在输入承诺和输出承诺。

证明:对通道的操作时原子的行为, 不能同一时刻创建同一通道的输入承诺和输出承诺, 在这里使用反证法证明。

当某一通道已经存在输出承诺时, 在这一通道上面执行输入动作, 将发生同步通信而不会产生输入承诺; 当某一通道已经存在输入承诺时, 在这一通道上面执行输出动作, 将发生同步通信而不会产生输出承诺。证明完毕。

3 整体架构及相关算法

3.1 整体架构

运行时环境的整体架构可以简单地通过一些数据结构和相关的算法来描述。基于Pi演算的并行编程语言的运行时环境的主要数据结构如下:

record scheduler

{

run:queue< process>

ready:queue< process>

wait:queue< process>

}

record process

{

env:array< value>

commits:array< commit>

def:definition

}

record channel

{

counter:int

commits:set< commit>

}

record commit

{

kind:{IN, OUT}

proc:process

chan:channel

val:value

}

scheduler是全局调度器数据结构, 其中包含三种状态的进程队列, 其中run队列大小和芯片核心数量相同, 是物理上可并行执行的进程数量, 是真正可以并行执行的进程数量; ready队列中的进程可以执行, 但是当前因为没有计算资源而没有被调度器调度, 当run队列中有进程执行结束后将从ready队列中选择进程放入run队列中执行; wait队列是阻塞的进程集合, 当前不可以执行, 可以被其他进程同步通信唤醒, 从wait队列转到ready队列, 也可能一直阻塞, 最后被垃圾回收算法回收。process是进程的数据结构, 其中包含进程的上下文环境和将要执行的后续进程定义, 其中进程上下文环境可以通过之前给定的公式静态计算。channel是通道数据结构, 通过引用计数器实现通道的回收, 通道结构中承诺集合是冗余信息, 它的作用是加快进程调度算法。commit是上面定义的承诺所对应的数据结构, 包含通道所属的进程, 通道的类型和通道上面传递的值等。

3.2 调度算法

并行进程调度算法是通过更新进程的状态, 不断选择可以执行的进程交给芯片的多个硬件核心并行执行的算法, 它是运行时环境设计的最核心的算法。调度算法执行就是不断更新scheduler结构的三种调度队列的过程。更新进程状态的依据是输入/输出前缀动作是否可以同步通信, 当可以同步通信时, 则继续执行后续进程, 并改变对应并行进程的状态; 当不能同步通信时, 当前进程将阻塞, 全局调度器把其从run状态改为wait状态, 并从ready队列选择新的可执行进程。算法如图1所示, 步骤如下:

	Figure Option View Download New Window
	图1 调度算法流程图Fig.1 Flow chart of scheduling algorithm

(1)run队列中进程数量小于芯片核心数时, 将ready队列中的进程填充到run队列中, 保持最大并行数。

(2)并行执行run队列中的进程具体动作:ⓐ当执行的动作是输入/输出前缀且满足recv/send操作语义时, 继续执行输入/输出前缀的后续进程; 并把对应的并行进程从wait队列中去除, 放入ready队列中。ⓑ当执行的动作是输入/输出前缀且满足in/out操作语义时, 则当前进程阻塞, 在上下文环境的承诺集合中加入输入/输出承诺, 然后把当前进程从run队列中去除, 添加到wait队列中; 从ready队列中选择新的进程添加到run队列中继续执行。

(3)run队列为空时, 回收wait队列中阻塞的进程集合, 并行程序终止。

在判断输入/输出前缀动作是否可以同步通信时, 可采用遍历全局调度器的wait队列中进程的上下文的承诺集合的方式寻找可同步的进程, 但是这种方法依托于wait队列的集中式查询方式执行速度和wait队列中进程数量是线性有关, 当进程较多时, 执行效率非常低。一种改进方式是在通道结构channel中加入该通道上的承诺集合, 直接通过查询通道的承诺集合查到对应的并行进程, 这个方式把之前的集中式的信息分散到各个通道里存储, 因此它的速度快, 而且采用非集中式的查询方式更适合于并行程序的调度。

3.3 垃圾回收算法

基于Pi演算的并行编程语言中通道是基础语义设施, 其他语言结构和相关算法都依托于这种基础设施。垃圾回收机制是运行时环境重要的资源管理算法, 也是现代编程语言的标志。本章分别给出基础语言设施的垃圾回收算法。它们都是基于引用计数器, 适合于并行程序设计^[4]。

3.3.1 通道的垃圾回收

通道是Pi演算中最重要的基本概念, 是本文中的并行编程语言中的进程相互通信的媒介和调度算法所依托的核心结构。如果运行时环境在没有垃圾回收机制的情况下并行程序不断申请新通道, 且不使用新的通道, 就会造成非常严重的内存泄漏可能最终导致程序异常退出。

垃圾回收算法如下:

$\begin{matrix} \begin{matrix} know s (\bar{c}, [Γ, δ] : P) = True if \exists x \in δ and δ (x) = \bar{c} \\ | False ot h erwise \\ globalrc (\bar{c}, Δ ∙ \prod_{i} [Γ_{i}, δ_{i}] : P_{i}) = \sum_{i} 1 if knows (\bar{c}, [Γ_{i}, δ_{i}] : P) \\ | 0 ot h erwise \\ \frac{globalrc (\bar{c}, A)}{Δ, \bar{c} ∙ A \to Δ ∙ A} (gc - c h annel) \\ \frac{\forall \bar{c} \in \cup Γ_{i}, globalrc (\bar{c}, \prod_{j} [Γ_{j}, δ_{j}] : Q_{j}) = 0}{Δ ∙ (\prod_{i} [Γ_{i}, δ_{i}] : \sum wait ‖ \prod_{j} [Γ_{j}, δ_{j}] : Q_{j}) \to Δ ∙ \prod_{j} [Γ_{j}, δ_{j}] : Q_{j}} (gc - process) \end{matrix} \end{matrix}$

公式knows用于计算某一进程是否引用某一通道, 公式globalrc计算某一通道被并行程序具体引用的次数。通道垃圾回收算法gc-channel表示当一个通道不被并行程序中的任何一个进程引用时, 那么此通道只是占用内存空间, 而没有被任何进程使用, 可以被运行时环境自动释放(即在全局环境中删除通道)。

算法具体实现时可以使用引用计数器处理, 如3.1节数据结构中counter成员记录通道被进程引用的次数。当创建一个新的通道时, 引用计数初始化为0, 传递通道时, 计数加1。进程终止时, 进程中通道的计数减1。当通道计数为0时, 表示通道没有被任何并行程序所引用, 可以释放该通道及其相关承诺信息。

3.3.2 进程的垃圾回收

上面介绍的通道垃圾回收算法, 可能存在由于循环引用而不能被通道的垃圾回收算法回收的问题。可用一种简单且有效的方法解决:在没有使原有算法复杂化的情况下, 只是把循环引用的垃圾回收问题转变为程序终止问题。即全局调度器中的wait队列表示阻塞的进程, 当run队列中没有进程可以继续执行时, 且wait队列还有进程时, wait队列中阻塞的进程将不能被其他运行的进程唤醒, 这时最简单的做法就是释放wait队列中阻塞的进程及进程的通道, 终止并行程序。

进程垃圾回收算法gc-process表示当一组进程集合都阻塞在自身进程上下文的承诺上, 不能和并行程序中的其他进程进行通信, 那么这组进程将无限地阻塞住。这种情况下最好的解决方法就是回收这组阻塞的进程。

在具体实现时, 借鉴通道的垃圾回收算法, 当检测某个阻塞的进程是否可以和其他进程通信时, 判断阻塞进程的承诺所在的通道引用计数是否为1, 如果为1表明通道只被自身引用不能和其他进程进行通信, 回收阻塞的进程; 如果非1表明进程被正在运行的进程引用, 可能被唤醒继续执行, 因此不可以被运行时环境回收。

通过引理1我们可以证明这种进程的垃圾回收算法是安全且完备的。即任一可运行的进程不会被回收, 所有不可运行的进程将被回收。

4 实验

并行程序定义如图2所示, 首先定义了两个进程Pinger和Ponger; 然后定义了main函数, 在main函数内部声明了全局通道ping和pong, 然后并行执行Pinger调用、Ponger调用和输出进程ping!(“ beep” )。

	Figure Option View Download New Window
	图2 并行程序源码Fig.2 Source code of parallel program

进程Pinger和Ponger的语义树如图3、图4所示, 在调用具体的进程定义时, 将解析对应语义树。并行程序main执行过程如下:

	Figure Option View Download New Window
	图3 Pinger语义树Fig.3 Pinger’ s semantic tree

	Figure Option View Download New Window
	图4 Ponger语义树Fig.4 Ponger’ s semantic tree

(1)执行new前缀语义, 创建全局通道ping和pong。

(2)执行par并行操作语义

a调用进程Pinger定义, 输入前缀不能进行同步通信而阻塞。

b调用进程Ponger定义, 输出前缀不能进行同步通信而阻塞。

c执行输出进程ping!(“ beep” ), 其唤醒Pinger进程; 输出进程执行结束。调度器执行Pinger进程, 其唤醒Ponger进程; Pinger执行结束。调度器执行Ponger进程。

(3)并行程序终止。

5 结束语

Pi演算是一种具有强大表达能力的移动并发进程演算。其本身的通道传递机制比传统的编程语言的共享内存机制更适合对并行程序通信模拟。虽然Pi演算对描述并行计算具有先天的语义优势, 但是目前完全基于Pi演算的编程语言只有Pict, 其是基于异步Pi演算语义。本文在Pi演算理论基础之上, 提出了一种以同步通信为核心, 基于Pi演算的并行编程语言的核心语义。并定义了并行进程的上下文环境, 在进程上下文环境基础上给出了运行时环境的整体架构及相关核心算法描述。在理论上定义了并行编程语言及其运行所需的环境。

The authors have declared that no competing interests exist.

参考文献

View Option

[1]	Sutter H. The free lunch is over: A fundamental turn toward concurrency in software[J]. Dr. Dobb's Journal, 2005, 30(3): 202-210. [本文引用:1]
[2]	康辉, 张双双, 梅芳. 一种递归π演算向Petri网的转换方法[J]. 吉林大学学报: 工学版, 2014, 34(1): 142-148. Kang Hui, Zhang Shuang-shuang, Mei Fang. Petri net translation of recursion π-calculus[J]. Journal of Jilin University(Engineering and Technology Edition), 2014, 34(1): 142-148. [本文引用:1]
[3]	Victor, Björn, Faron Moller. The Mobility Workbench-a Tool for the π-calculus[M]. Computer Aided Verification, Heidelberg: Springer Berlin, 1994. [本文引用:1]
[4]	Paz H, Petrank E, Bacon D F, et al. An efficient on-the-fly cycle collection[C]∥Compiler Construction, Springer, Berlin Heidelberg, 2005: 156-171. [本文引用:2]
[5]	Honda K, Tokoro M. An object calculus for asynchronous communication[C]∥European Conference on Object-Oriented Programming. Springer Berlin Heidelberg, 1991: 133-147. [本文引用:1]
[6]	Boudol G. Asynchrony and the Pi-calculus[R]. INRIA Research Report 1702, 1992. [本文引用:1]
[7]	郝克刚, 郭小群. Pi 演算对图灵机的表达[J]. 计算机工程与科学, 2009, 31(10): 53-55. Hao Ke-gang, Guo Xiao-qun. Expression of turing machines by pi calculus[J]. Computer Engineering & Science, 2009, 31(10): 53-55. [本文引用:1]
[8]	Milner R, Parrow J, Walker D. A calculus of mobile processes, parts I and II[J]. Information and Computation, 1992, 100(1): 151-175. [本文引用:1]
[9]	Sangiorgi D. A theory of bisimulation for the π-calculus[J]. Acta Informatica, 1996, 33(1): 69-97. [本文引用:1]
[10]	Pierce B C, Turner D N. Pict: a programming language based on the Pi-Calculus[C]∥Proof, Language, and Interaction, 2000: 455-494. [本文引用:1]

2005

0.0

... s Journal上发表《免费午餐已经结束》^[1]一文以来,科研工作者已经认识到如果未来不能有效地以并行化的软件充分利用并行化的多核硬件资源,计算效率将永远停滞在略高于当前的水平上 ...

2014

0.0