• Articles • Previous Articles     Next Articles

Cooperating CoScheduling: A Coscheduling Proposal Aimed at Non-Dedicated Heterogeneous NOWs

Francesc Giné1, Francesc Solsona1, Mauricio Hanzich2, Porfidio Hernández2, and Emilio Luque2   

  1. 1Department of Computer Science, Universitat de Lleida, Spain 2Department of Computer Architecture & Operating Systems, Universitat Autònoma de Barcelona, Spain
  • Received:2007-01-09 Revised:2007-07-02 Online:2007-09-10 Published:2007-09-10

Implicit coscheduling techniques applied to non-dedicated homogeneous Networks Of Workstations (NOWs) have shown they can perform well when many local users compete with a single parallel job. Implicit coscheduling deals with minimizing the communication waiting time of parallel processes by identifying the processes in need of coscheduling through gathering and analyzing implicit runtime information, basically communication events. Unfortunately, implicit coscheduling techniques do not guarantee the performance of local and parallel jobs, when the number of parallel jobs competing against each other is increased. Thus, a low efficiency use of the idle computational resources is achieved. In order to solve these problems, a new technique, named Cooperating CoScheduling (CCS), is presented in this work. Unlike traditional implicit coscheduling techniques, under CCS, each node takes its scheduling decisions from the occurrence of local events, basically communication, memory, Input/Output and CPU, together with foreign events received from cooperating nodes. This allows CCS to provide a social contract based on reserving a percentage of CPU and memory resources to ensure the progress of parallel jobs without disturbing the local users, while coscheduling of communicating tasks is ensured. Besides, the CCS algorithm uses status information from the cooperating nodes to balance the resources across the cluster when necessary. Experimental results in a non-dedicated heterogeneous NOW reveal that CCS allows the idle resources to be exploited efficiently, thus obtaining a satisfactory speedup and provoking an overhead that is imperceptible to the local user.

Key words: Java Beaus; semantic constraints; specification; dynamic checking;

[1] Acharya A, Edjlali G, Saltz J. \rm The utility of exploiting idle workstations for parallel computations. In -\it Proc. the ACM SIGMETRICS/PERFORMANCE}, USA, 1997, pp.225$\sim$236.

[2] Acharya A, Setia S. \rm Availability and utility of idle memory in workstation clusters. In -\it Proc. the ACM SIGMETRICS/PERFORMANCE}, USA, 1999, pp.35$\sim$46.

[3] Carriero N, Freedman E, Gelernter D, Kaminsky D. Adaptive parallelism and piranha. -\it Computer}, 1995, 28(1): 40$\sim$49.

[4] Litzkow M, Livny M, Mutka M. Condor --A hunter of idle workstations. In -\it Proc. the 8th Int. Conf. Distributed Computing Systems}, USA, 1988, pp.104$\sim$111.

[5] Ousterhout J. Scheduling strategies for concurrent systems. In -\it Proc. the 3rd Int. Conf. Distributed Computing Systems}, USA, 1982, pp.22$\sim$30.

[6] Feitelson D. Packing schemes for gang scheduling. -\it Lecture Notes in Computer Science}, 1996, 1162: 89$\sim$110.

[7] Sobalvarro P, Weihl W. Demand-based coscheduling of parallel jobs on multiprogrammed multiprocessors. -\it Lecture Notes in Computer Science}, 1995, 949: 106$\sim$126.

[8] Anglano C. A comparative evaluation of implicit coscheduling strategies for networks of workstations. In -\it Proc. the 9th Int. Symp. High Performance Distributed Computing}, Japan, 2000, pp.221$\sim$228.

[9] Sobalvarro P, Pakin S, Weihl W, Chien A. Dynamic coscheduling on workstation clusters. -\it Lecture Notes in Computer Science}, 1998, 1459: 231$\sim$256.

[10] Frachtenberg E, Feitelson D, Petrini F, Fernandez J. Flexible CoScheduling: Mitigating load imbalance and improving utilization of heterogeneous resources. In -\it Proc. the Int. Parallel and Distributed Processing Symposium $($IPDPS$)$}, France, 2003.

[11] Hanzich M, Gin\'e F, Hern\'andez P \it et al. \rm %, F. Solsona, E. Luque. Coscheduling and multiprogramming level in a non-dedicated cluster. -\it Lecture Notes in Computer Science}, 2004, 3241: 327$\sim$336.

[12] Sodan A. Loosely coordinated coscheduling in the context of other approaches for dynamic job scheduling: A survey. -\it Concurrency and Computation: Practice and Experience}, 2005, 17(16): 1725$\sim$1781.

[13] Petrini F, Feng W. Buffered coscheduling: A new methodology for multitasking parallel jobs on distributed systems. In -\it Proc. the Int. Parallel and Distributed Processing Symposium $($IPDPS$)$}, Mexico, 2000.

[14] Solsona F. Coscheduling techniques for non-dedicated cluster computing
[Dissertation]. Dept. Computer Science, Universitat Autonoma de Barcelona, Spain, 2002.

[15] Dusseau A. Implicit coscheduling: Coordinated scheduling with implicit information in distributed systems. -\it ACM Transactions on Computer Systems}, 2001, 19(3): 283$\sim$331.

[16] Nagar S, Banerjee A, Sivasubramaniam A, Das C. Alternatives to coscheduling a network of workstations. -\it J. Parallel and Distributed Computing}, 1999, 59: 302$\sim$327.

[17] Choi G, Agarwal S, Kim J, Yoo A, Das C. Impact of job allocation strategies on communication-driven coscheduling in clusters. -\it Lecture Notes in Computer Science}, 2003, 2790: 160$\sim$169.

[18] Frachtenberg E, Petrini F, Feitelson D, Fernandez J. Adaptive parallel job scheduling with flexible coscheduling. -\it IEEE Trans. Parallel and Distributed Systems}, 2005, 16(11): 1066$\sim$1077.

[19] Yu J, Azougagh D, Kim J, Maeng S. \rm Impact of exploiting load imbalance on coscheduling in workstation clusters. In -\it Proc. the Int. Conference on Parallel Processing $($ICPP$)$}, Norway, 2005, pp.595$\sim$602.

[20] Du X, Zhang X. Coordinating parallel processes on networks of workstations. -\it J. Parallel and Distributed Computing}, 1997, 46(2): 125$\sim$135.

[21] Gin\'e F, Solsona F, Hern\'andez P, Luque E. Dealing with memory constraints in a non-dedicated linux cluster. -\it International Journal of High Performance Computing Applications}, 2003, 17(1): 39$\sim$48.

[22] Nikolopoulos D, Polychronopoulos C. Adaptive scheduling under memory constraints on a non-dedicated computational farms. -\it Future Generation Computer Systems}, 2003, 19(4): 505$\sim$519.

[23] Ryu K, Pachapurkar N, Fong L. \rm Adaptive memory paging for efficient gang scheduling of parallel applications. In -\it Proc. the Int. Parallel and Distributed Processing Symposium $($IPDPS$)$}, Mexico, 2004, pp.30$\sim$40.

[24] Gin\'e F, Solsona F, Hern\'andez P, Luque E. Cooperating CoScheduling in a non-dedicated cluster. -\it Lecture Notes in Computer Science}, 2004, 2790: 212$\sim$218.

[25] Zhang X, Yan Y. Modeling and characterizing parallel computing performance on heterogeneous NOW. In -\it Proc. the Seventh IEEE Symposium on Parallel and Distributed Processing}, USA, 1995, pp.25$\sim$34.

[26] Mutka M, Livny M. The available capacity of a privately owned workstation environment. -\it J. Performance Evaluation}, 1991, 12(4): 269$\sim$284.

[27] Nielsen J. Designing Web Usability: The Practice of Simplicity. New Riders Publishing, 2000.

[28] Batat A, Feitelson D. \rm Gang scheduling with memory considerations. In -\it Proc. the 14th Int. Parallel Distributed Processing Symposium (IPDPS)}, Mexico, 2000, pp.109$\sim$114.
[1] Jing-Xuan Zhang, Chuan-Qi Tao, Zhi-Qiu Huang, Xin Chen. Discovering API Directives from API Specifications with Text Classification [J]. Journal of Computer Science and Technology, 2021, 36(4): 922-943.
[2] Jia-Qi Yin, Hui-Biao Zhu, Yuan Fei. Specification and Verification of the Zab Protocol with TLA+ [J]. Journal of Computer Science and Technology, 2020, 35(6): 1312-1323.
[3] Gianna Reggio, Maurizio Leotta, Filippo Ricca, Diego Clerissi. DUSM: A Method for Requirements Specification and Refinement Based on Disciplined Use Cases and Screen Mockups [J]. Journal of Computer Science and Technology, 2018, 33(5): 918-939.
[4] Qian Wu (吴倩), Guang-Tai Liang (梁广泰), Qian-Xiang Wang (王千祥), Member, CCF, ACM, IEEE and Hong Mei (梅宏), Fellow, CCF. Mining Effective Temporal Specifications from Heterogeneous API Data [J]. , 2011, 26(6): 1061-1075.
[5] Giuseppe Lami and Robert W. Ferguson. An Empirical Study on the Impact of Automation on the Requirements Analysis Process [J]. , 2007, 22(3): 338-347 .
[6] Nelly Condori-Fernandez, Silvia Abrahao, and Oscar Pastor. On the Estimation of the Functional Size of Software from Requirements Specifications [J]. , 2007, 22(3): 358-370 .
[7] WU Guoqing(毋国庆),SHU Fengdi(舒风笛),WANG Min(王敏)and CHEN Weiqing(陈伟清). Requirements Specifications Checking of Embedded Real-Time Software [J]. , 2002, 17(1): 0-0.
[8] WANG Yunfeng(王云峰),PANG Jun(庞军),ZHA Ming(查鸣),YANG Zhaohui(杨朝晖)and ZHENG Guoliang(郑国梁). A Formal Software Development Approach Using Refinement Calculus [J]. , 2001, 16(3): 0-0.
[9] LI Li(李黎). Towards a Denotational Semantics of Timed RSL Using Duration Calculus [J]. , 2001, 16(1): 0-0.
[10] LUAN Shangmin; LI wei;. An Incremental Approach toAutomatic Algorithm Design [J]. , 1999, 14(4): 314-319.
[11] NI Bin; FENG Yulin;. Dynamic Checking Frameworkfor Java Beaus Semantic Constraints [J]. , 1999, 14(4): 408-413.
[12] CHEN Haiming;. Function Definition Language FDL andIts Implementation [J]. , 1999, 14(4): 414-421.
[13] WU Guoqing; LIU Xiang; YING Shi; Tetsuo Tamai;. Automated Analysis of the SCR-StyleRequirements Specifications [J]. , 1999, 14(4): 401-407.
[14] CAI Jiamei;. The Sequence Modeling Method Based on ECCin Developing Program Specifications [J]. , 1999, 14(4): 337-348.
[15] Lin Hong; Chen Guoliang;. Program Constructionby Verifying Specification [J]. , 1998, 13(6): 597-607.
Full text



[1] Mei Wen , Nan Wu, Hai-Yan Li, and Chun-Yuan Zhang. Multiple-Morphs Adaptive Stream Architecture[J]. , 2005, 20(5): 635 -646 .
[2] Ali A. Alwan, Hamidah Ibrahim, and Nur Izura Udzir. Improved Integrity Constraints Checking in Distributed Databases by Exploiting Local Checking[J]. , 2009, 24(4): 665 -674 .
[3] Michael Q. Zhang and Andrew D. Smith, Member, ACM . Challenges in Understanding Genome-Wide DNA Methylation[J]. , 2010, 25(1): 26 -34 .
[4] Cheng-Lin Fan, Jun Luo, Wen-Cheng Wang, Fa-Rong Zhong, Binhai Zhu. On some proximity problems of colored sets[J]. , 2014, 29(5): 879 -886 .
[5] Ling-Da Li, Jun-Lin Lu, Xu Cheng. Retention Benefit Based Intelligent Cache Replacement[J]. , 2014, 29(6): 947 -961 .
[6] Hai-Da Zhang, Zhi-Hao Xing, Lu Chen, Yun-Jun Gao, Senior Member, CCF, Member, ACM, IEEE. Efficient Metric All-k-Nearest-Neighbor Search on Datasets Without Any Index[J]. , 2016, 31(6): 1194 -1211 .
[7] Qing Jiang, Hang-Yu Hu, Guang-Min Hu. Two-Type Information Fusion Based IP-to-AS Mapping Table Refining[J]. , 2017, 32(3): 571 -584 .
[8] Shu-Quan Wang, Lei Wang, Yu Deng, Zhi-Jie Yang, Sha-Sha Guo, Zi-Yang Kang, Yu-Feng Guo, Wei-Xia Xu. SIES: A Novel Implementation of Spiking Convolutional Neural Network Inference Engine on Field-Programmable Gate Array[J]. Journal of Computer Science and Technology, 2020, 35(2): 475 -489 .
[9] Mohammad Y. Mhawish, Manjari Gupta. Predicting Code Smells and Analysis of Predictions: Using Machine Learning Techniques and Software Metrics[J]. Journal of Computer Science and Technology, 2020, 35(6): 1428 -1445 .
[10] Xue-Qi Li, Guang-Ming Tan, Ning-Hui Sun. PIM-Align:A Processing-in-Memory Architecture for FM-Index Search Algorithm[J]. Journal of Computer Science and Technology, 2021, 36(1): 56 -70 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved