Queueing theory based modeling and optimal scheduling in Map-Reduce-like Frameworks

FORK-JOIN QUEUE MODELING AND OPTIMAL SCHEDULING IN PARALLEL PROGRAMMING FRAMEWORKS

ABSTRACTMapReduce framework is widely used to parallelize batch jobs since it exploits a high degree of multi-tasking to process them. However, it has been observed that when the number of servers increases, the map phase can take much longer than expected. This thesis analytically shows that the stochastic behavior of the servers has a negative effect on the completion time of a MapReduce job, and continuously increasing the number of servers without accurate scheduling can degrade the overall performance. We analytically model the map phase in terms of hardware, system, and application parameters to capture the effects of stragglers on the performance. Mean sojourn time (MST), the time needed to sync the completed tasks at a reducer, is introduced as a performance metric and mathematically formulated. Following that, we stochastically investigate the optimal task scheduling which leads to an equilibrium property in a datacenter with different types of servers. Our experimental results show the performance of the different types of schedulers targeting MapReduce applications. We also show that, in the case of mixed deterministic and stochastic schedulers, there is an optimal scheduler that can always achieve the lowest MST.

KEYWORDS
ᐧ

Comments

Post a Comment

Popular posts from this blog

System and methods for UICC-based secure communication

ABSTRACT A system that incorporates the subject disclosure may include, for example, instructions which when executed cause a device processor to perform operations comprising sending a service request to a remote management server; receiving from the management server an authentication management function and an encryption key generator for execution by a secure element and an encryption engine for execution by a secure device processor, sending a request to establish a communication session with a remote device; and communicating with the remote device via a channel established using an application server. The secure element and the secure device processor authenticate each other using a mutual authentication keyset. The secure element, the secure device processor and the device processor each have a security level associated therewith; the security level associated with the secure device processor is intermediate between that of the secure element and that of the device processor....
Read more

Computer Vision Keywords

2D attacks 2D Face 2D Face Authentication 3D blood flow estimation 3D Face 3D Face Localisation 3D face model 3D face recognition 3D localization 3D Masks 3D model base indexing 3D object recognition abnormality detection accelerated exact k-means Accent Identification Accented speech Accentual mismatch accessible games acoustic frequency Acoustic model adaptation acoustic modeling Acoustic reverberation sparsity models Acoustic reverberation structures Acoustic signal processing acoustic stream acquisition ACT metric activation function active shape model activity Actor–critic Ad hoc array calibration Ad hoc microphone array calibration Adaboost adalaine adaptive exploration/exploitation trade-off adaptive learning rate adaptive resonance theory adaptive steepness Addressee estimation Adequacy of diffuseness Ad-hoc microphone array Adhoc microphone array calibration Ad-hoc microphone array calibration Ad-hoc microphone calibration AFC A...
Read more