Tag Archives: Optimization

Stochastic Modeling and Optimization of Stragglers

Abstract: MapReduce 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 paper 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.

Authors: Farshid Farhat and Diman Zad Tootaghaj from Penn State, Yuxiong He from MSR (Microsoft Research)

. The work was done during my visit from MSR in Summer 2015.

Stochastic modeling and optimization of stragglers in mapreduce framework

@phdthesis{farhat2015stochastic,
  title={Stochastic modeling and optimization of stragglers in mapreduce framework},
  author={Farhat, Farshid},
  year={2015},
  school={The Pennsylvania State University}
}

Stochastic modeling and optimization of stragglers

@article{farhat2016stochastic,
  title={Stochastic modeling and optimization of stragglers},
  author={Farhat, Farshid and Tootaghaj, Diman and He, Yuxiong and Sivasubramaniam, Anand and Kandemir, Mahmut and Das, Chita},
  journal={IEEE Transactions on Cloud Computing},
  year={2016},
  publisher={IEEE}
}

Optimal Placement in Network On-Chip

Leave a reply

Abstract:
Parallel programming is emerging fast and intensive applications need more resources, so there is a huge demand for on-chip multiprocessors. Accessing L1 caches beside the cores are the fastest after registers but the size of private caches cannot increase because of design, cost and technology limits. Then split I-cache and D-cache are used with shared LLC (last level cache). For a unified shared LLC, bus interface is not scalable, and it seems that distributed shared LLC (DSLLC) is a better choice. Most of papers assume a distributed shared LLC beside each core in on-chip network. Many works assume that DSLLCs are placed in all cores; however, we will show that this design ignores the effect of traffic congestion in on-chip network. In fact, our work focuses on optimal placement of cores, DSLLCs and even memory controllers to minimize the expected latency based on traffic load in a mesh on-chip network with fixed number of cores and total cache capacity. We try to do some analytical modeling deriving intended cost function and then optimize the mean delay of the on-chip network communication. This work is supposed to be verified using some traffic patterns that are run on CSIM simulator.

Full text @ OPCCMCNOC

Performance Modeling and Optimization of MapReduce

Leave a reply

Abstract:
MapReduce framework is widely used to parallelize batch jobs of great companies. MapReduce splits the job for each mapper in the map phase and then intermediate tasks are synced in reducers to be processed in the next stage. It exploits a high degree of multi-tasking to process the jobs as soon as possible. However map and reduce phases are done by many parallel nodes, it has been realized that when the number of mappers increase map phase takes longer than usual. This problem known as stragglers issue has been observed in CDF of completion times of mapper nodes.
This paper shows that stochastic behavior of mapper nodes has a negative effect on the completion time of MapReduce framework, i.e. increasing the number of mapper nodes blindly not only manages resources effectively but also can degrade the performance. To the best of our knowledge this is the first time in this paper MapReduce framework is modeled as fork-join queues from HDFS storage to one reducer. We capture the stragglers problem and based on observed delayed exponential CDF of response time of mappers we model task inter-arrival and service rate of each mapper node. Mean sojourn time (MST) which is the time needed to sync the completed map tasks at one reducer is formulated. Then we minimize MST by finding the input mapping of jobs to each mapper node. Equilibrium of means as a property of MST minimization problem can be generalized to some other inter-arrival and service time distributions. In the case of mixed deterministic and stochastic modeling optimal solution can always show the lowest MST. This approach not only can capture the optimal mapping of mapper nodes but also can address the optimal number of mapper nodes to get the lowest response time by MapReduce framework.

Performance Modeling and Optimization of MapReduce