The week's pick
Random Articles
Reseach Article
Minimal Task Allocation in Multiprocessors using improved next-fit for RM scheduling
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 47 - Number 19 |
| Year of Publication: 2012 |
| Authors: Muthu Kumar B, Anju S Pillai |
10.5120/7299-0546
|
Muthu Kumar B, Anju S Pillai . Minimal Task Allocation in Multiprocessors using improved next-fit for RM scheduling. International Journal of Computer Applications. 47, 19 ( June 2012), 36-44. DOI=10.5120/7299-0546
Abstract
Task-processor allocation in multiprocessors can be accomplished efficiently for reducing the required number of processors for the given task set, accounting reduced power consumption with maximum processor utilization. This work is based on next fit algorithm using Rate Monotonic Algorithm (RMA) for a fixed priority system. The work proposes a minimal task allocation algorithm for multiprocessor environment. The proposed method reduces the number of processors required for a given task set using improved next fit algorithm and the same has been evaluated and tested. The proposed algorithm gives better results when there is large number of tasks in the system.
References
- WANG Tao and LIU Da-Xin. "The Performance Evaluation of Rate Monotonic Tasks Assignment Algorithms on Multiprocessor," Computer Science, China, Vol. 34, pp. 272-276, 2007.
- A. Abraham, R. Buyya, and B. Nath. Nature's heuristics for scheduling jobs on computational grids. In The 8th IEEE International Conference on Advanced Computing and Communications (ADCOM 2000), India, 2000.
- S. K. Dall and C. L. Liu, "On a Real-Time Scheduling Problem,"Operations Research, vol. 6, no. 1, pp. 127-140, 1978.
- A. Burchard, J. Liebeherr, Y. Oh, and S. H. Son, "New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems," IEEE Trans. Computers, vol. 44, no. 12, pp. 1429-1441, Dec. 1995.
- D. Peng, K. Shin, and T. Abdelzaher, "Assignment and Scheduling Communicating Periodic Tasks in distributed Real-Time Systems," Trans. Software Eng. , vol. 23, no. 12, pp. 745-758, Dec. 1997.
- Satoshi Fujita, "A Branch-and-Bound Algorithm for solving the Multiprocessor Scheduling Problem with Improved Lower Bounding Techniques," in IEEE Transactions on computers, Vol. 60, No. 7, July 2011.
- S. K. Baruah and J. Goossens, "Rate-Monotonic Scheduling on Uniform Multiprocessors," IEEE Trans. Computers, vol. 52, no. 7, pp. 966-970, July 2003.
- C. L. Liu and J. W. Layland, "Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment," J. ACM, vol. 20, no. 1, pp. 46-61, 1973.
- Jose´ M. Lo´pez, Jose´ L. D?´az, and Daniel F. Garc?´a, "Minimum and Maximum utilization bounds for multiprocessor Rate Monotonic scheduling," IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 7, 2004.
- BEAUVAIS, Jean-Pime; DEPLANCHE, Anne-Marie; , "A Task Allocation Algorithm In a Multiprocessor Real-Time System," Parallel Processing, 1993. ICPP 1993. International Conference on , vol. 2, no. , pp. 130-133, 16-20 Aug. 1993.
- Wei, T. ; Mishra, P. ; Wu, K. ; Liang, H. ; , "Fixed-Priority Allocation and Scheduling for Energy-Efficient Fault Tolerance in Hard Real-Time Multiprocessor Systems," Parallel and Distributed Systems, IEEE Transactions on , vol. 19, no. 11, pp. 1511-1526, Nov. 2008.
- Lin Huang; Feng Yuan; Qiang Xu; , "Lifetime reliability-aware task allocation and scheduling for MPSoC platforms," Design, Automation & Test in Europe Conference & Exhibition, 2009. DATE '09. , vol. , no. , pp. 51-56, 20-24 April 2009.
- Tongquan Wei; Yonghe Guo; Xiaodao Chen; Shiyan Hu;, "Adaptive task allocation for multiprocessor SoCs," Quality Electronic Design (ISQED), 2010 11th International Symposium on , vol. , no. , pp. 538-543, 22-24 March 2010.
- Jia Huang; Raabe, A. ; Buckl, C. ; Knoll, A. ; , "Runtime adaptive allocation of dynamically mixed tasks on a heterogeneous MPSoC platform," Design and Architectures for Signal and Image Processing (DASIP), 2010 Conference on , vol. , no. , pp. 34-41, 26-28 Oct. 2010.
- Jia Huang; Buckl, C. ; Raabe, A. ; Knoll, A. ; , "Energy-Aware Task Allocation for Network-on-Chip Based Heterogeneous Multiprocessor Systems," Parallel, Distributed and Network-Based Processing (PDP), 2011 19th Euromicro International Conference on , vol. , no. , pp. 447-454, 9-11 Feb. 2011.
- Suganya, K. ; Nagarajan, V. ; , "Efficient run-time task allocation in reconfigurable multiprocessor System-on-Chip with Network-on-Chip," Computer, Communication and Electrical Technology (ICCCET), 2011 International Conference on , vol. , no. , pp. 12-17, 18-19 March 2011.
- Jia Huang; Raabe, A. ; Buckl, C. ; Knoll, A. ; , "A workflow for runtime adaptive task allocation on heterogeneous MPSoCs," Design, Automation & Test in Europe Conference & Exhibition (DATE), 2011 , vol. , no. , pp. 1-6, 14-18 March 2011.
- Sudharshan K Dhall, "Approximation algorithms for scheduling Time-critical jobs on Multiprocessor systems," University of oklahoma, by CRC press,2004.
- Shinpei Kato and Nobuyuki Yamasaki, "Real Time Scheduling with Task Splitting on Multiprocessors," in 8th IEEE International conference on Embedded and Real-Time computing systems and Applications, RTCSA 2007.
- Enrico Bini and Giorgio C. Buttazzo, "Measuring the Perfomance of Schedulability Tests," in Springer science, Real-Time systems, 30, pp. 145-147, 2005.
Index Terms
Keywords