Cost-effective Job-splitting in Parallelized Systems

September 05, 2017 – ,

<g class="gr_ gr_24 gr-alert gr_gramm gr_inline_cards gr_run_anim Grammar only-ins replaceWithoutSep" id="24" data-gr-id="24">Ubiquitous</g> presence of parallel systems (also, Fork-Join systems) in this age of high-performance computing makes them a topic of great research interest. Few popular implementations of such systems are Apache Spark, Hadoop <g class="gr_ gr_25 gr-alert gr_gramm gr_inline_cards gr_run_anim Punctuation only-ins replaceWithoutSep" id="25" data-gr-id="25">and</g> Multipath TCP. In a Fork-Join system, jobs are split into tasks as they arrive and are assigned to one of the parallel servers. A job leaves the system when all of its constituent tasks are finished. A common metric of performance for such systems is the time a job has to wait in the system. This quantity is random and dependent on the dynamics of the job arrivals, i.e., how jobs enter the systems and the dynamics of the server capacities, i.e., how fast workers process their tasks. In this thesis, however, we intend to focus on cost-effective ways of splitting incoming jobs subject to the waiting time. With some assumptions on cost structure as per server usage (e.g. cost model of Amazon EC2 virtual machines), we seek to explore splitting strategies under the constraint of costs. The first step would be to find a scheduling strategy assuming linear cost per server along with simple job arrival and worker service time. Thereafter, we may look for further generalizations. There will be <g class="gr_ gr_28 gr-alert gr_gramm gr_inline_cards gr_run_anim Grammar only-ins doubleReplace replaceWithoutSep" id="28" data-gr-id="28">opportunity</g> to collaborate with Prof P. Kuehn (Universitaet Stuttgart) while working on this thesis.

download corresponding tendering

Keywords: Queueing Theory

Research Area(s):

Tutor: Sounak Kar,

Open Theses