计算机科学 ›› 2016, Vol. 43 ›› Issue (6): 82-85.doi: 10.11896/j.issn.1002-137X.2016.06.017

• 目次 • 上一篇    下一篇

基于多核的并行操作转换算法

黎明丽,蔡维纬,吕晓,何发智   

  1. 武汉大学 武汉400072,武汉大学 武汉400072,武汉大学 武汉400072,武汉大学 武汉400072
  • 出版日期:2018-12-01 发布日期:2018-12-01
  • 基金资助:
    本文受湖北省自然科学基金(2015CFB254)资助

Parallel Operational Transformation Algorithm in Multi-core

LI Ming-li, CAI Wei-wei, LV Xiao and HE Fa-zhi   

  • Online:2018-12-01 Published:2018-12-01

摘要: 操作转换算法是实时协同编辑系统首选的并发控制算法,它不仅能提供不受限的交互,而且维护分布式操作的意图一致性。然而随着操作数目的增多,操作的响应时间也会延长。结合多核多线程技术的发展,提出了第一个并行的操作转换算法,其能减少远程操作集成到本地站点的时间开销。对传统的串行算法进行了改造,使得具有计算依赖的过程能够并行化。实验结果表明,提出的算法相较于传统算法具有较大的优势,在处理较大操作历史的情况下依然能够保证操作合理的响应时间。

关键词: 操作转换,并行计算,多核多线程,实时协同编辑,数据一致性

Abstract: Operational transformation algorithm is the first choice of real-time collaborative editing systems.As a concurrency control strategy,it not only supports unconstrained interactions,but also maintains the intention consistency of distributed operations.However,as the number of executed operations increases,the performance degrades,affecting the responsive time of operations.Combining the development of multi-core and multi-threading,this paper proposed the first parallel operational transformation algorithm,which can greatly reduce the time costs of integrating remote operations.The traditional sequential algorithm is modified,so that the procedure with computation-dependency can be parallelized.Extensive experiments show that the proposed algorithm takes large advantage over the traditional algorithm,and even though the operation history is very large,it still provides a decent responsive time.

Key words: Operational transformation,Parallel computing,Multi-core and multi-threading,Real-time collaborative editing,Data coherence

[1] Leslie L.Time,clocks,and the ordering of events in a distributed system[J].Communications of the ACM,1978,21(7):558-565
[2] Sun Cheng-zheng,Xia S,Sun D,et al.Transparent adaptation of single-user applications for multi-user real-time collaboration[J].ACM Transactions on Computer-Human Interaction,2006,13(4):531-582
[3] Wang Xue-yi,Bu Jia-jun,Chen Chun.Achieving undo in bitmap-based collaborative graphics editing systems[C]∥ACM Confe-rence on Computer Supported Cooperative Work.2002:68-76
[4] Ignat C-L,Norrie Moira C.Customizable collaborative editor relying on treeOPT algorithm[C]∥European Conference on Computer-Supported Cooperative Work.2003:315-334
[5] Liu Hua-jun,He Fa-zhi,Li Xiao-xia,et al.A less constraint concurrency control and consistency maintaince in collaborative CAD system[J].Chinese Journal of Electronics,2013,22(1):15-20
[6] Agustina,Sun Cheng-zheng,Xu Dong.Operational transformation for dependency conflict resolution in real-time collaborative 3D design systems[C]∥ACM conference on Computer Supported Cooperative Work.2012:1401-1410
[7] Ellis C A,Gibbs S J.Concurrency control in groupware systems[C]∥ACM SIGMOD International Conference on Management of Data.1989:399-407
[8] Yang Guang-xin,Shi Mei-lin.Object Data Model Based Concurrency Control in Fully-Replicated Architecture[J].Chinese Journal of Computers,2000,23(2):113-125(in Chinese) 杨光信,史美林.全复制结构下基于对象数据模型的并发控制[J].计算机学报,2000,23(2):113-125
[9] Matthias R,Doris N-R,Gunzenuser G R.An integrating transformation-oriented approach to concurrency control and undo in group editors[C]∥ACM Conference on Computer Supported Cooperative Work.1996:288-297
[10] Randolph A,Boucheneb H,Imine A,et al.On Synthesizing a Consistent Operational Transformation Approach[J].IEEE Transactions on Computers,2015,64(4):1074-1089
[11] Sun Cheng-zheng,Jia Xiao-hua,Zhang Yan-chun,et al.Achie-ving convergence,causality preservation,and intention preservation in real-time cooperative editing systems[J].ACM Transactions on Computer-Human Interaction,1998,5(1):63-108
[12] Liao Bin,He Fa-zhi,Jing Shu-xu.Survey of Operational Transformation Algorithms in Real-time Computer Supported Coope-rative Work[J].Journal of Computer Research and Development,2007,44(2):326-333(in Chinese) 廖斌,何发智,荆树旭.实时协同工作系统中操作转换算法综述[J].计算机研究与发展,2007,4(2):326-333
[13] Li Du,Li Rui.An admissibility-based operational transformation framework for collaborative editing systems[J].Computer Supported Cooperative Work,2010,19(1):1-43
[14] Imine Abdessamad.A Flexible concurrency control for real-time collaborative editors[C]∥International Conference on Distributed Computing Systems Workshops.2008:423-428

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!