PERFORMANCE EVALUATION OF DYNAMIC SHARING OF PROCESSORS IN 2-STAGE PARALLEL PROCESSING SYSTEMS

In this paper, we first study the performance of job scheduling in a l arge parallel processing system where a job is modeled as a concatenat ion of two stages which must be processed in sequence. We denote Pi as the number of processors required by stage i and denote P as the tota l number of processors in the system. The service time requirement of stage i, given the required Pi processors, is exponentially distribute d with mean 1/mu(i). Hence, a job can be fully described by a quadrupl e (P1, P2, mu1, mu2). Three service disciplines which can fully utiliz e all processors in the system are studied in this paper. We first con sider a large parallel computing system where Max(P1, P2) greater-than -or-equal-to P much greater than 1 and Max(P1, P2) >> Min(P1, P2). For such systems, exact expressions for the mean system delay are obtaine d for various job models and disciplines. Our results show that the pr iority should be given to jobs working on the stage which requires few er processors. We then relax the large parallel system (i.e., P much g reater than 1) condition to obtain the mean system time for two job mo dels when the priority is given to the second stage. Moreover, a Scale -up Rule is introduced to obtain the approximated delay performance wh en the system provides more processors than the maximum number of proc essors required by both stages (i.e., P > Max(P1, P2)). Lastly, an app roximation model is given for jobs with more than two stages.