You are here

Home » Content

Algorithmic Presentation in Order to Resource Scheduling on Graph According to Time and Cost Parameters with High Computing Power of Graphic Processor

Journal Name:

  • International Journal of Science and Engineering Investigations

Publication Year:

  • 2017

Key Words:

Author NameUniversity of Author
Abstract (2. Language): 
Using CUDA computer programing and performing this algorithm on graphics processor increase the speed considerably. According to high computing power of graphics processors, this algorithm was turned to CUDA language to be able to be calculated by graphics processor unit and increase the speed of calculations. After implementing and performing different tests we witnessed the considerable difference in performance time and manifold speed of algorithm on graphics processing unit toward central process unit. The main constrain during designing optimization is time constraint. There are other constraints such as size, energy consumption and so on during scheduling. Time budget management is employed for different designing operations such as cables and gates sizing and providing library map. This paper aims at presenting an algorithm which can perform the resources scheduling on graph according to time and cost parameters in a reasonable period in a way to have the fastest form with the lowest cost. So, at first the cheapest maximum flow is introduced which is one of the most applicable discussions. The important point in using this algorithm is to find and replacing the parameters of flow and cost so that this replacement can solve the considered problem absolutely optimal. The next step is to implement the algorithm in an acceptable way. First we implement this algorithm in C++ language and the next step is to implement this algorithm on graphics processing unit.
Bookmark/Search this post with
FULL TEXT (PDF): 
PDF icon arastirmax-algorithmic-presentation-order-resource-scheduling-graph-according-time-and-cost-parameters-high-computing-power-graphic-processor.pdf
  • 12
57
65
  • Turkish

REFERENCES

References: 

[1] A. Kahng, S.Mantik, and I.L. Markov. (2002) “Min-Max Placement for Large- Scale Timing Optimization”, In the proceedings of ACM International Symposium on Physical Design, pp. 143-148.
[2] Barron J, Fleet DJ, Beauchemin S. (1994) Performance of Optical Flow Techniques. Int'l J Comp Vision. 12:43–77.
[3] C. Chen, E. Bozorgzadeh, A. Srivastava, and Majid Sarrafzadeh.(2002) “Budget Management with Applications”. In Algorithmica, vol 34, No. 3, pp. 261- 275.
[4] C. Chen, X. Yang, M. Sarrafzadeh. (2000) “Potential Slack: An Effective Metric of Combinational Circuit Performance. In the proceedings of ACM/IEEE International Conference on Computer-Aided Design, pp. 198-201.
[5] C. Kuo and A. C.-H Wu. (2000)“Delay Budgeting for a Timing-Closure-Design Method”, In the proceedings of International Conference on Computer- Aided Design, pp. 202 207.
[6] Chetverikov D. (2003) Applying feature tracking to Particle Image Velocimetry. International Journal of Pattern Recognition and Artificial Intelligence. 17:487–504.
International Journal of Science and Engineering Investigations, Volume 6, Issue 71, December 2017 65
www.IJSEI.com Paper ID: 67117-09
ISSN: 2251-8843
[7] E. Bozorgzadeh, S. Ghiasi, A Takahashi, and M. Sarrafzadeh. (2004) ”Optimal Integer Delay Budget Assignment on Directed Acyclic Graphs”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,Vol. 23, No.xx,.
[8] Ford, L.R., Jr.; Fulkerson, D.R. (1962), Flows in Networks, Princeton University Press.
[9] Ford,L.R.; Fulkerson, D. R.(1956) "Maximal flow through a network". Canadian Journal of Mathematics 8: 399, 1956.
[10] Gass, Saul I.; Assad, Arjang A. (2005) "Mathematical, algorithmic and professional developments of operations research from 1951 to 1956". An Annotated Timeline of Operations Research. International Series in Operations Research & Management Science 75. pp. 79–110.
[11] Goldberg, A., Tarjan, R.,(1988) A New Approach to the Maximum-flow Problem, Journal of the Association for Computing Machinery 35, 4, 921–940.
[12] H. R. Lin and T. Hwang.(1995) “Power Reduction by Gate Sizing with Path- Oriented Slack Calculation”. In the proceedings of ‘IEEE ASP-DAC, pp. 7 12.
[13] H. Szymanski,(2013) "Max-Flow Min-Cost Routing in a Future-Internet with Improved QoS Guarantees", In the proceedings of IEEE Transactions on Communication, Vol. 61, No.4.
[14] H. Youssef, E. Shragowitz. (1955) “Timing Constraints for Correct Performance”, In the proceedings of ACM/IEEE International Conference on Computer-Aided Design, 1990.
[15] Harris, T. E.; Ross, F. S. "Fundamentals of a Method for Evaluating Rail Net Capacities". Research Memorandum (Rand Corporation).
[16] http://www.wikipedia.com
[17] Hu W, Tan T, Wang L, Maybank S. (2004) A Survey on Visual Surveillance of Object Motion and Behaviors. IEEE Transactions on Systems, Man, and Cybernetics. 34:334–352.
[18] J. Luo and N. Jha. (2001) ”Battery-Aware Static Scheduling for Distributed Real-Time Embedded Systems”. In the proceedings of IEEE/ACM Design Automation Conference.
[19] Kelner, J. A.; Lee, Y. T.; Orecchia, L.; Sidford, A. (2014). "An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations". Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 217.
[20] Knight, Helen. (2014) "New algorithm can dramatically streamline solutions to the ‘max flow’ problem". MIT News. Retrieved 8 January.
[21] M. Sarrafzadeh, D. Knol, and G. Tellez.(1997) “Unification of Budgeting and Placement” In the proceedings of ACM/IEEE Design Automation Conference, June 1997.
[22] M.Hulkkonen.(2011), "Graphics Processing Unit Utilization in Circuit Simulation ",.Master's Thesis. Aalto University School of Electrical Engineering, August.
[23] M.Sarrafzadeh, D. A. Knol, G.E. Tellez. (1997)“A Delay Budgeting Algorithm Ensuring Maximum Flexibility in Placement In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, , Vol. 16, No. 11 , pp. 1332 -1341, Nov.
[24] Matov, M. Edvall, Ge Yang, and G. Danuser. (2011) "Optimal-Flow Minimum-Cost Correspondence Assignment in Particle Flow Tracking". Comput Vis Image Underst.; 115(4): 531–540, Apr.
[25] Medioni G, Cohen I, Bremond F, Hongeng S, Nevatia R.(2001) Event Detection and Analysis from Video Streams. IEEE Transactions on Pattern Analysis and Machine Intelligence. 23:873–889.
[26] Micheli ED, Torre V, Uras S. (1993) The accuracy of the computation of optical flow and of the recovery of motion parameters. IEEE Trans Pattern Anal Mach Intell. 15:434–447.
[27] Morris BT, Trivedi MM. (2008) A Survey of Vision-Based Trajectory Learning and Analysis for Surveillance. IEEE Transactions on Curcuits and Systems for Video Technology. 18:114–1127..
[28] S. Bakshi and D. Gajski. (1996) “Component Selection for High-Performance Pipelines”. In IEEE Transactions on Very Large Scale Integrated Systems, pp. 181-194, Vol. 4, No. 2.
[29] S. Chen, C, Chern, (2000) "Max-Flow Min-Cost Algorithm for A Supply Chain Network", In the proceedings of APDSI 2000 Full Paper, July..
[30] S. Ghiasi, K. Nguyen, E. Bozorgzadeh, and M. Sarrafzadeh. (2003) ”On Computation and Resource Management in an FPGA-based Computing Environment”. a poster presentation in ACM International Symposium on Field-Programmable Gate Arrays (FPGA), February.
[31] S. L. Lin and J. Allen. (1986) “MinPlex- A Compactor that Minimizes the Rounding Rectangle and Individual Rectangles in a Layout”. In the proceedings of ACM/IEEE Design Automation Conference, pp. 123-130.
[32] Schrijver, A. (2002) "On the history of the transportation and maximum flow problems". Mathematical Programming 91 (3): 437–445.
[33] Schwartz, B. L. (1966). "Possible Winners in Partially Completed Tournaments". SIAM Review 8 (3): 302.
[34] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.(2006) "Maximum Flow". Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. pp. 643–668. ISBN 0-262-03293-7.
[35] W. Zhang, N. Vijaykrishnan, M. Kandemir, M. J. Irwin, D. Duarte, and Y. Tsai.(2001) ”Exploiting VLIW schedule slacks for dynamic and leakage energy reduction ”. In the proceedings of IEEE International Symposium on Microarchitecture, 2001.
[36] Moavenian, K. (2012) "implementing several examples of parallel algorithm using multi-core graphic cards", Payam Noor University, Mashhad.

Thank you for copying data from http://www.arastirmax.com