Wednesday, May 10, 2017

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

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

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 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

Tuesday, May 9, 2017

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

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 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
Stochastic processes, Computational model, Delayed Tailed Distribution, Optimal scheduling, Cloud computing, Synchronization, Queuing Theory, MapReduce, Stochastic Modeling, Performance Evaluation, Fork-Join Queue.

Thursday, April 27, 2017

Farshid Farhat 's Site @ PSU

Farshid Farhat 's Site @ PSU

Publications

  • Security Weaknesses in PGP Protocol, F Farhat, M Heydari, MR Aref, 2013.

Thursday, August 25, 2016

Diman Zad Tootaghaj 's publications


  1. 1.D. Z. Tootaghaj, F. Farhat. Optimal placement of Cores, Caches and Memory controllers in NoC. arXiv, 2016. [link] [pdf]
  2. 2.F. Farhat, D. Z. Tootaghaj, M. Arjomand. Towards optimizing data computing in the cloud. arXiv, 2016. [link] [pdf]
  3. 3. F. Farhat, D. Z. Tootaghaj, Y. He, A. Sivasubramaniam, M. T. Kandemir, C. R. Das. Stochastic modeling and optimization of stragglers. IEEE transaction on Cloud Computing (TCC), 2016. [link] [pdf]
  4. 4.D. Z. Tootaghaj,  Evaluating cloud workload characteritics. Master’s thesis, The Pennsylvania State University, 2015. [link] [pdf]
  5. 5.D. Z. Tootaghaj, F. Farhat, M. Arjomand, P. Faraboschi, M. T. Kandemir, A. Sivasubramaniam, C. R. Das, Evaluating the Combined Impact of Datacenter Architecture and Cloud Workload Characteristics on Performance, Network Traffic and Cost, IEEE International Symposium on Workload Characterization (IISWC) 2015. [link] [pdf]
  6. 6.F. Farhat, D. Z. Tootaghaj, A. Sivasubramaniam, M. T. Kandemir, C. R. Das, Modeling and Optimization of Straggling Mappers.Technical Report CSE-14-006, Pennsylvania State University. [link] [pdf]
7. D. Z. Tootaghaj, F. Farhat, M. R. Pakravan, M. R. Aref, Risk of Attack Coefficient Effect on Availability of Ad-hoc Networks, IEEE CCNC Research Student Workshop, 2011. [link] [pdf]
8. D. Z. Tootaghaj, F. Farhat, M. R. Pakravan, M. R. Aref, Game-Theoretic Approach to Mitigate Packet Dropping in Wireless Ad-hoc Networks, IEEE CCNC Research Student Workshop, 2011. [link] [pdf]
9. M. A. Kashiha, D. Z. Tootaghaj, Partial Discharge Source Classification and De-noising in Rotating Machines Using Discrete Wavelet Transform and Directional Coupling Capacitor, Journal of Electromagnetic Analysis and Applications and submitted and accepted to Asia-Pacific Power and Engineering Conference (APPEEC), sponsored by IEEE Power & Energy Society (PES), March 2009. [link] [pdf]

Towards Stochastically Optimizing Data Computing Flows

Optimal Placement of Cores Caches and MemoryControllers in NoC

Friday, November 7, 2014

Bad children and a box of beverage bottles!

D. and F. provided one beverage box with 32 bottles for the weekend party, but one of their four children changed the content of one of the bottles that cannot be detected easily! To punish the children, they decided to permute the bottles and ask the children to find it again until two days later! Unfortunately if one drinks from THAT bottle, he/she will be sick tomorrow for a week, but the children like to participate in the party very much! What is the best strategy for the children?

Bad children and a box of beverage!

D. and F. provided one beverage box with 32 bottles for the weekend party, but one of their four children changed the content of one of the bottles that cannot be detected easily! To punish the children, they decided to permute the bottles and ask the children to find it again until two days later! Unfortunately if one drinks from THAT bottle, he/she will be sick tomorrow for a week, but the children like to participate in the party very much! What is the best strategy for the children?


What is the best strategy?


Monday, February 11, 2013

Farshid Farhat (fuf111 at cse psu edu)

Farshid Farhat @ Computer Science and Engineering Dep. of Pennsylvania State University
Farshid Farhat CSE
Farshid Farhat PSU

Wednesday, January 2, 2013

No "Transcend" just lose and fail!

I had bought two external Transcend HDs, that after 6 months both of them failed!
No "Transcend" just lose and fail!