楊旭超

摘要： 基于一個(gè)專門程序環(huán)境的科學(xué)工作流，對(duì)組織層級(jí)的比較分析進(jìn)行了研究。結(jié)合科學(xué)工作流在S-P樹變換與測(cè)度中的運(yùn)用，為組織層級(jí)的比較分析提供了系統(tǒng)科學(xué)的處理辦法：通過對(duì)不同組織層級(jí)之間的最小變換進(jìn)行測(cè)度，為組織變革的代價(jià)提供一定程度的參考。

關(guān)鍵詞： 科學(xué)工作流； S-P樹； 變換與測(cè)度； 組織層級(jí)

中圖分類號(hào)：G301文獻(xiàn)標(biāo)志碼:A文章編號(hào)：1006-8228（2012）03-28-03

Comparison analysis of organization levels based on scientific workflow

Yang Xuchao1，2

（1. HangZhou DianZi University HangZhou ZheJiang 310018， China； 2. ZheJiang Technology Institute of Economy）

Abstract： The author studies in this paper scientific workflows based on a specific program of environment, and provides a more convenient and effective method to solve practical problems in operation research and computer sciences. Combining the application of scientific workflows in transformation and measurement of S-P tree, the author presents a systematic and scientific method to comparison analysis of organizational levels. It provides in some sense a reference for organizational reforming cost analysis through measuring the minimal transformation between various organization levels.

Key words： scientific workflow; S-P tree; transformation and measurement; organization levels

1 科學(xué)工作流概述

信息時(shí)代的特征是，知識(shí)信息與科研數(shù)據(jù)呈指數(shù)級(jí)增長，科學(xué)實(shí)驗(yàn)規(guī)模越來越大，基于虛擬環(huán)境下的科學(xué)研究方法日益復(fù)雜。在計(jì)算機(jī)技術(shù)與網(wǎng)絡(luò)技術(shù)深入發(fā)展和廣泛應(yīng)用的今天，科學(xué)家往往需要使用許許多多的應(yīng)用程序?qū)Υ罅康脑紨?shù)據(jù)或中間數(shù)據(jù)進(jìn)行研究分析，需要頻繁地對(duì)海量數(shù)據(jù)進(jìn)行操作處理。

科學(xué)工作流(Scientific Workflow, SWF)提供了一個(gè)專門的程序環(huán)境，以減少科研人員中進(jìn)行研究的投入[1]。因此，科學(xué)工作流已成為在網(wǎng)絡(luò)基礎(chǔ)設(shè)施上進(jìn)行大規(guī)模科學(xué)計(jì)算和協(xié)同研究的有效方法。

科學(xué)工作流的研究主要圍繞科學(xué)計(jì)算、網(wǎng)格等展開[2]，內(nèi)容涉及科學(xué)工作流在具體應(yīng)用環(huán)境中的解決方案，科學(xué)工作流的建模，來源管理，系統(tǒng)可視化，語言，數(shù)據(jù)流控制[2]以及科學(xué)工作流管理系統(tǒng)( Scientific Workflow Management Systems，SWFMS)[5]的開發(fā)和優(yōu)化等幾個(gè)方面。

科學(xué)工作流管理系統(tǒng)提供了一個(gè)科學(xué)計(jì)算流程定義和自動(dòng)運(yùn)行的管理平臺(tái)[5]。通過定義各個(gè)活動(dòng)調(diào)用資源，在活動(dòng)之間建立數(shù)據(jù)流關(guān)系和控制流關(guān)系，借助該平臺(tái)可以完成特定的科學(xué)計(jì)算問題。

作為一種輔助科學(xué)家進(jìn)行科學(xué)實(shí)驗(yàn)的手段, 科學(xué)工作流管理系統(tǒng)是對(duì)多領(lǐng)域或?qū)ｉT領(lǐng)域科學(xué)工作流進(jìn)行管理的系統(tǒng)，涉及到多任務(wù)協(xié)調(diào)執(zhí)行的活動(dòng)，旨在定義、執(zhí)行并監(jiān)控整個(gè)活動(dòng)過程，解決領(lǐng)域應(yīng)用的具體問題及優(yōu)化以往的研究成果，為促進(jìn)和保障虛擬知識(shí)環(huán)境下的科研協(xié)作提供一種解決方案[2]。

科學(xué)工作流管理系統(tǒng)應(yīng)具有有以下主要特點(diǎn)：

⑴ 具有計(jì)算集成、分析集成、數(shù)據(jù)集成、應(yīng)用集成與大規(guī)模并行化等特點(diǎn)?？梢越M合不同領(lǐng)域的復(fù)雜應(yīng)用程序，按照一定的規(guī)則在分布式計(jì)算資源上對(duì)海量數(shù)據(jù)進(jìn)行查找、移動(dòng)、分析、處理、存儲(chǔ)、 仿真以及可視化操作[5]。

⑵ 適應(yīng)應(yīng)用的分布式和異構(gòu)性[3]?？茖W(xué)計(jì)算中問題求解過程可能涉到不同系統(tǒng)之間的協(xié)作，而系統(tǒng)之間是分布式的，系統(tǒng)構(gòu)架很難統(tǒng)一，加大了應(yīng)用集成的難度。Web服務(wù)[8]對(duì)這類應(yīng)用的封裝可以有效解決這方面的問題，但封裝過程通常比較復(fù)雜。

⑶ 適應(yīng)各種應(yīng)用的特殊性、易用性和靈活性[3]。科學(xué)計(jì)算中常常涉及大量的數(shù)據(jù)計(jì)算，且計(jì)算資源難以提供統(tǒng)一接口，隨著應(yīng)用類型的增加，用戶需要不斷熟悉各類應(yīng)用集成和使用方法，某些應(yīng)用要有較高的執(zhí)行性能。

⑷ 適應(yīng)應(yīng)用間數(shù)據(jù)格式的差異性[3]。應(yīng)用有不同格式的輸入/輸出，為了保證數(shù)據(jù)流在不同應(yīng)用間的正確傳遞，用戶需要花費(fèi)大量精力開發(fā)數(shù)據(jù)格式的轉(zhuǎn)換代碼。

顯見，科學(xué)工作流系統(tǒng)的特點(diǎn)是面向數(shù)據(jù)流，側(cè)重高度密集的數(shù)據(jù)計(jì)算、分析與處理[3], 而且應(yīng)用集成是科學(xué)工作流系統(tǒng)的一個(gè)顯著特征。本文結(jié)合S-P樹的科學(xué)工作流作變換分析，根據(jù)對(duì)科學(xué)工作流變換的適當(dāng)測(cè)度，可以反映不同科學(xué)工作流之間的差距，為科學(xué)工作流的程序化實(shí)現(xiàn)提供了可能，從而解決一些科學(xué)工作流的最小變換代價(jià)問題。

2 科學(xué)工作流的變換與測(cè)度

將典型的S-P樹變換成注釋的S-P樹如圖1所示可以方便科學(xué)工作流之間的變換[6]。

圖1科學(xué)工作流的變換

具體看一個(gè)組織的管理層級(jí)變換過程以→∧表示刪除枝葉，∧→表示添加枝葉，則管理層級(jí)T1變換到T2的過程可以描述為：

⑴

圖2T1組織層級(jí)

圖3T2組織層級(jí)

對(duì)Ｓ-Ｐ圖有以下幾類基本的操作。

序列操作（用Ｓ表示）：子集的序列合成。

平行操作（用Ｐ表示）：平行操作包括了平行層面的一支或兩支結(jié)點(diǎn)的所有的并集操作。

叉操作（用Ｆ表示）：叉操作要求結(jié)點(diǎn)下有一個(gè)或多個(gè)子結(jié)點(diǎn)，并對(duì)子結(jié)點(diǎn)進(jìn)行平行處理。首先在叉點(diǎn)（數(shù)據(jù)源處），將數(shù)據(jù)分離，再在校準(zhǔn)點(diǎn)處接合，以平行生成一個(gè)或多個(gè)子集。子集當(dāng)中可以存在差異。

對(duì)于平行操作，記M為初始狀態(tài)T1和最終狀態(tài)T2之間的過渡匹配變量，M中的一對(duì)結(jié)點(diǎn)（v1，v2）如果滿足以下兩個(gè)條件，就稱做不穩(wěn)定匹配：

條件1：（v1，v2）是一對(duì)P結(jié)點(diǎn)；條件2：v1、v2都只有一個(gè)子結(jié)點(diǎn)，這對(duì)子節(jié)點(diǎn)同類且未被M所匹配。

相對(duì)應(yīng)的，不穩(wěn)定匹配的對(duì)立面就是穩(wěn)定匹配。

給出一個(gè)來自T1與T2之間良好匹配的M，以及M中的一對(duì)子節(jié)點(diǎn)（v1，v2），使得M（v1，v2）成為T1[v1]到T2[v2]的相應(yīng)匹配，我們可以將匹配消耗γ（M（v1，v2））作如下定義：

如果（v1，v2）穩(wěn)定匹配，則有：

⑵

如果（v1，v2）不穩(wěn)定匹配，則有：

⑶

上列各式中，c1、c2分別是v1、v2的子集，I1、I2分別是M在T1與T2之間的匹配結(jié)點(diǎn)集，XT(c)表示刪除子枝T[c]的最小消耗，是刪除h(v1)子枝的最小消耗，其中h(v1)的子枝不同于T[c]的子枝h(c1)。

3 不同組織層級(jí)的比較分析

3.1 組織層級(jí)概述

由于組織管理的需要，組織層級(jí)化成為組織管理的必然趨勢(shì)。組織層級(jí)化是指組織在縱向結(jié)構(gòu)設(shè)計(jì)中需要確定層級(jí)數(shù)目和有效的管理幅度，根據(jù)組織集權(quán)化的程度，規(guī)定縱向各層級(jí)之間的權(quán)責(zé)關(guān)系，最終使組織具有一個(gè)能夠?qū)?nèi)外環(huán)境要求做出動(dòng)態(tài)反應(yīng)的有效結(jié)構(gòu)。

由于組織任務(wù)存在遞減性，從最高層的直接主管到最低的基層具體工作人員之間就形成了一定的層次，這種層次便稱為組織層級(jí)[7]。

3.2 程序設(shè)計(jì)

程序設(shè)計(jì)思路如下：

以M*（v1，v2）變量作為T1[v1]與T2[v2]之間的最小消耗匹配變量，s為計(jì)數(shù)器。

如果v1與v2完全相等，返回M*（v1，v2）的值，不作相應(yīng)處理；反之，不作處理，進(jìn)入下一階段循環(huán)。如果v1與v2均為序列結(jié)點(diǎn)，將v1、v2的子結(jié)點(diǎn)序列合成結(jié)果M*（c1，c2）添加到M*（v1，v2）內(nèi)，計(jì)數(shù)器進(jìn)行計(jì)數(shù)，反之，不處理，進(jìn)入下一階段循環(huán)。如果v1與v2均為平行結(jié)點(diǎn)，分兩種情況處理：

情形一：如果v1、v2均有一個(gè)結(jié)點(diǎn)c1、c2,選擇滿足⑷式的M*（c1，c2）返回M*（v1，v2）內(nèi)，計(jì)數(shù)器進(jìn)行計(jì)數(shù)，以達(dá)到最小消耗，反之，按情形二處理；

⑷

情形二：進(jìn)行的選擇，并將M*（c1，c2）返回M*（v1，v2）內(nèi)，計(jì)數(shù)器進(jìn)行計(jì)數(shù)，反之，進(jìn)入下一階段循環(huán)。

如果v1與v2均為叉結(jié)點(diǎn)，對(duì)M*（c1，c2）進(jìn)行最小適配處理，將M*（c1，c2）返回M*（v1，v2）內(nèi)，計(jì)數(shù)器進(jìn)行計(jì)數(shù)。最后返回程序結(jié)果。

設(shè)計(jì)測(cè)度程序如下：

AlgorithmEdit-Distance-on-Trees

Input: T1[v1] and T2[v2] such that h(v1) =h(v2)

Output: M*（v1，v2）: the minimum-cost well-formed mapping

from T1[v1] toT2[v2] and s

1: add（v1，v2） to M*（v1，v2）

2:s=0

3: ifthen

4: return M*（v1，v2）

5: end if

6: if then

7: for each pair of children （c1，c2） of v1 and v2 do

8: add M*（c1，c2） to M*（v1，v2） and s=s+1

9: end for

10: end if

11: ifthen

12: if both v1 and v2 have only one child, say c1 and c2,

andthen

13: ifthen

14: add M*（c1，c2） to M*（v1，v2） and s=s+1

15: end if

16: else

17: for each pair of children （c1，c2） of v1 and v2 such

thatanddo

18: add M*（c1，c2） to M*（v1，v2） and s=s+1

19: end for

20: end if

21: end if

22: ifthen

23: B*:=the minimum-cost bipartite matching

24: for each pair of children （c1，c2） of v1 and v2 such that

do

25: add M*（c1，c2） to M*（v1，v2） and s=s+1

26: end for

27: end if

28: return M*（v1，v2） and s

利用返回M*（v1，v2）值與s可以得到不同管理層級(jí)之間的最小變換代價(jià)以及變換的最小次數(shù)。進(jìn)一步地，通過M*（c1，c2）值與s大小，我們也可以得到不同管理層級(jí)之間的最小變換成本，可為組織變革的代價(jià)提供一定程度的參考。

參考文獻(xiàn)：

[1] Taylor I J, Deelman E, Gannon D B. Workflows for E-Science[M].

New York: Springer, 2007.

[2] 蘇明明.2007-2008年國外科學(xué)工作流研究進(jìn)展[J]. 國外研究進(jìn)展_

圖書館建設(shè),2009.7:96~100

[3] 汪春杰.面向科學(xué)工作流的應(yīng)用集成框架[J].計(jì)算機(jī)工程,2009.10:

258~263

[4] 羅海濱.工作流技術(shù)綜述[J].軟件學(xué)報(bào),2000.11:899~907

[5] 張衛(wèi)民.科學(xué)工作流技術(shù)研究綜述[J].國防科技大學(xué)學(xué)報(bào),2011.6:

56~65

[6] Zhuowei Bao、Sarah Cohen-Boulakia、Susan B.Davidson、Anat

Eyal、Sanjeev Khanna.Differencing.Provenance in Scientific Workflows[J]. IEEE International Conference on Data Engineering,2009:808~815

[7] 周三多.管理學(xué)[M].高等教育出版社,2005.