基于科學工作流的組織層級比較分析

楊旭超

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

關鍵詞： 科學工作流； S-P樹； 變換與測度； 組織層級

中圖分類號：G301文獻標志碼:A文章編號：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 科學工作流概述

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

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

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

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

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

科學工作流管理系統(tǒng)應具有有以下主要特點：

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

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

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

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

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

2 科學工作流的變換與測度

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

圖1科學工作流的變換

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

⑴

圖2T1組織層級

圖3T2組織層級

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

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

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

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

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

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

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

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

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

⑵

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

⑶

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

3 不同組織層級的比較分析

3.1 組織層級概述

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

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

3.2 程序設計

程序設計思路如下：

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

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

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

⑷

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

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

設計測度程序如下：

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可以得到不同管理層級之間的最小變換代價以及變換的最小次數(shù)。進一步地，通過M*（c1，c2）值與s大小，我們也可以得到不同管理層級之間的最小變換成本，可為組織變革的代價提供一定程度的參考。

參考文獻：

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

New York: Springer, 2007.

[2] 蘇明明.2007-2008年國外科學工作流研究進展[J]. 國外研究進展_

圖書館建設,2009.7:96~100

[3] 汪春杰.面向科學工作流的應用集成框架[J].計算機工程,2009.10:

258~263

[4] 羅海濱.工作流技術綜述[J].軟件學報,2000.11:899~907

[5] 張衛(wèi)民.科學工作流技術研究綜述[J].國防科技大學學報,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] 周三多.管理學[M].高等教育出版社,2005.