Prof. Dr. Paul J. Kühn
Lecturer Prof. Dr. Paul J. Kühn(University of Stuttgart)
Title Analyses of Fork-Join Models with and without Blocking by the Method of Task Graph Reduction
Date Thursday 06/12/2018, 10.00 – 11.00
Location S3|20 Rundeturmstr. 10, Darmstadt
Room 111
Abstract
Fork-Join (FG) -Problems appear in systems with parallel computation or parallel communication and have raised research interests since about 4 decades by researchers of computer science and stochastic performance evaluation. The key challenges of the theoretical analysis are synchronization conditions which may cause server blocking and performance degradation which limit the full exploitation of parallel computation or parallel communication. Fundamental theories on the performance of such system models have been reported based on stochastic ordering principles and min-plus algebra (“Network Calculus”).

In this contribution an alternative analysis method is presented based on a stochastic task graph reduction (TGR) method for cases where tasks of a job are statistically independent of each other. Exact and approximate solutions are presented for both, Blocking and Non-Blocking FG-models. In Blocking FJ-problems all parallel tasks of a job begin their execution simultaneously; the next job can only be started, when the previous job has completely finished, i.e., servers which become idle remain blocked until all parallel tasks of a job have been executed. Servers in Non-Blocking FJ-problems can be scheduled for processing of succeeding jobs immediately after finishing a task, i.e., enforced idle times are avoided.

Exact solutions for Blocking FJ-models lead through the TGR method to queuing models of the type GI/G/1, where the equivalent service time is generally distributed, i.e., for all exact solutions known for GI/G/1 queuing models as, e.g., of types M/M/1, M/G/1, GI/M/1, and GI/G/1 where arrival and service processes are represented by phase-type distributions or models with batch arrival processes of type M[x]/G/1. For the residual GI/G/1 queuing models reliable approximate solutions exist at least for mean delays. All solutions are likewise exactly valid for queue service disciplines FIFO (First-In,First-Out), LIFO (Last-In,First-Out) or RANDOM order of service.

Non-Blocking FG-models lead also to GI/G/1 queuing models where the execution times of virtualized parallel tasks are flow (or sojourn) times of individual task queuing models of the type GI/G/1. This problem is harder than the problem for Blocking problems. Exact solutions are provided for parallel M/M/1 and GI/M/1 queuing models. Approximate solutions can be obtained from GI/G/1 approximations where the first moment (mean tW) and the coefficient of variation cW of waiting times are known from which the sojourn time cumulative distribution functions (CDF) can be approximated by the Weibull-DF and for which tabled results are existing.

Finally, numerical results on the probability density function (PDF) and CDF for both FG-models will be reported which have been worked out within a student research study project by Felix Reppin.
Bio
Study in Electrical Engineering and Communications, University of Stuttgart, Germany
* Dr.-Ing. and Dr.-Ing.habil. Degrees from University of Stuttgart (US)
* Head Research Group on Network Performance, University of Stuttgart, 1973 – 1977
* Member Technical Staff, AT&T Bell Laboratories, Holmdel, NJ, USA, 1977 -1978
* Chair Communication Systems and Networks, University of Siegen, Germany, 1979 -1983
* Chair and Director Institute Communication Networks and Computer Engineering (IKR) University of Stuttgart, 1983 – 2009
* Professor Associe, ENST Paris since1992
* Professor emeritus at University of Stuttgart since 2009
* Founding Dean Faculty “Information Engineering and Technology (IET), German University in Cairo (GUC) 2002 -
* Coordinator/Chair of Study Commission of the Int. MSc.Program ”Information Technology“. University of Stuttgart, 1999 -2012
* Dean Faculty of EE, Univ. of Siegen, 1980-81, Uni. of Stuttgart, 1986-87
* Dear Faculty of Computer Science, Electrical Engineering and Infirmation Technology, University of Stuttgart, 2002 – 2006
* Member Council of the German University in Cairo (GUC), 2003 – 2016

* Member of Heidelberger Academy of Sciences, Germany,since 1992
* Member of Academy Technical Sciences (acatec), Germany, since 1996
* Member of German National Academy of Science Leopoldina, since 1996
* Member IEEE, ACM, VDE, ITG, GI, IFIP-WGs. 6.2 and 7.3
* Member GI/ITG Committee Distributed Systems and Communication, since early 80-ies
* Member GI/ITG Committee Measurement and Modeling of Computer and Communication Systems
* Member of Committee ITG 5.2 (Communication Networks), 1986 – 1998
* Member of Committee ITG 5.1 (Information Theory) since 2010

* Fellow IEEE, 1989, Life Fellow IEEE since 2009
* Dr.h.c., Lund University of Technology, Sweden, 2006
* Dr.-Ing.E.h. Technical University of Dresden, Germany, 2008
* Honorary Senator, University of Mannheim, Germany, 1998
* Christo Columbus Gold Medal, Council City of Genua, Italy, 1998
* Chevalier Ordre Palmes Academique, French Government, 2002
* Eduard-Rhein-Price, Germany, 2003
* Honorary Member, Verband Deutscher Elektrotechniker (VDE), Germany, 2008
* Arne Jensen Lifetime Achievement Award, Int. Teletraffic Congress (ITC), 2010
* Fellow ITG, 2018

* Chairman of the International Advisory Council (IAC), International Teletraffic Congress (ITC), 1991 – 2007
* Chairman of the Advisory Board of the Center for Telematics and Information Technology (CTIT), University of Twente, The Netherlands, 1995 – 2000
* Chairman of the Advisory Board ITeG (Information Technology Design, University of Kassel, since 2010
* Member Supervisory Council, Krone AG, Berlin, 1988- 1992
* Member Supervisory Council, Bosch Telecom, Frankfurt/Main, 1092- 1996
* Coordinator Industrial Advisory Group CAMPUS, Siemens Enterprise Networks/UNIFY, 2007 -
* Coordinator EU-Project RACE 1022, 1988 – 1994
* Coordinator DFG-Center Program Mobile Communications, 1993 – 1999
* Coordinator of DFG Graduate College Program on Distributed Systems and Communications, 1993 – 2002
* Vice-Chairman, DFG-Cooperative Research Center ”NEXUS" on Context-sensitive Systems, University of Stuttgart, 2001-2008
* Doctoral and Habilitation Thesis Advisor of more than 80 researchers