Distributed order scheduling and its application to multi-core dram controllers

ABSTRACT

We study a distributed version of the order scheduling problem that arises when scheduling memory requests in shared DRAM systems of many-core architectures. In this problem, a set of n customer orders needs to be scheduled on multiple facilities. An order can consist of multiple requests, each of which has to be serviced on one designated facility, and an order is completed only when all its requests have been serviced. In the distributed setting, every facility has its own request buffer and must schedule the requests having only limited knowledge about the buffer state at other facilities In this paper, we quantify the trade-off between the amount of communication among different facilities and the quality of the resulting global solution. We show that without communication, the average completion time of all orders can be by a factor Ω(√n) worse than in the optimal schedule. On the other hand, there exists a 2-approximation algorithm if the complete buffer states are exchanged in n communication rounds. We then prove a general upper bound that characterizes the region between these extreme points. Specifically, we devise a distributed scheduling algorithm that, for any k, achieves an approximation ratio of O(k) in n/k communication rounds. Finally, we empirically test the performance of our different algorithms in a many-core environment using SPEC CPU2006 benchmarks as well as Windows desktop application traces.

REFERENCES

• 1: Sanjay Bhansali , Wen-Ke Chen , Stuart de Jong , Andrew Edwards , Ron Murray , Milenko Drinić , Darek Mihočka , Joe Chau, Framework for instruction-level tracing and analysis of program executions, Proceedings of the 2nd international conference on Virtual execution environments, June 14-16, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134760.1220164]
• 2: Z. L. Chen and N. G. Hall. Supply Chain Scheduling: Assembly Systems. Working Paper, Department of Systems Engineering, University of Pennsylvania, 2000.
• 3: I. Duenyas. Estimating the Throughput of Cyclic. Management Science, 39:616--625, 1993.
• 4: J. M. Frailong, W. Jalby, and J. Lenfant. "XOR-Schemes: A flexible data organization in parallel memories". In Proc. of International Conference on Parallel Processing (ICPP), 1985.
• 5: N. Garg, A. Kumar, and V. Pandit. Order Scheduling Models : Hardness and Algorithms. In Proc. of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2007.
• 6: T. Karkhanis and J. E. Smith. A day in the life of a data cache miss. In Workshop on Memory Performance Issues, 2002.
• 7: Tejas S. Karkhanis , James E. Smith, A First-Order Superscalar Processor Model, Proceedings of the 31st annual international symposium on Computer architecture, p.338, June 19-23, 2004, München, Germany
• 8: Joseph Y. Leung , Haibing Li , Michael Pinedo, Order Scheduling in an Environment with Dedicated Resources in Parallel, Journal of Scheduling, v.8 n.5, p.355-386, October 2005 [doi>10.1007/s10951-005-2860-x]
• 9: Joseph Y. -T. Leung , Haibing Li , Michael Pinedo, Scheduling orders for multiple product types to minimize total weighted completion time, Discrete Applied Mathematics, v.155 n.8, p.945-970, April, 2007 [doi>10.1016/j.dam.2006.09.012]
• 10: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 11: Micron. 1Gb DDR2 SDRAM Component: MT47H128M8HQ-25, May 2007.
• 12: Thomas Moscibroda , Onur Mutlu, Memory performance attacks: denial of memory service in multi-core systems, Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, p.1-18, August 06-10, 2007, Boston, MA
• 13: Onur Mutlu , Hyesoon Kim , Yale N. Patt, Efficient Runahead Execution: Power-Efficient Memory Latency Tolerance, IEEE Micro, v.26 n.1, p.10-20, January 2006 [doi>2006-02-17 02:00:03.800]
• 14: Onur Mutlu , Thomas Moscibroda, Stall-Time Fair Memory Access Scheduling for Chip Multiprocessors, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.146-160, December 01-05, 2007 [doi>10.1109/MICRO.2007.40]
• 15: Onur Mutlu , Thomas Moscibroda, Parallelism-Aware Batch Scheduling: Enhancing both Performance and Fairness of Shared DRAM Systems, Proceedings of the 35th International Symposium on Computer Architecture, p.63-74, June 21-25, 2008
• 16: Kyle J. Nesbit , Nidhi Aggarwal , James Laudon , James E. Smith, Fair Queuing Memory Systems, Proceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture, p.208-222, December 09-13, 2006 [doi>10.1109/MICRO.2006.24]
• 17: C. T. Ng , T. C. E. Cheng , J. J. Yuan, Concurrent open shop scheduling to minimize the weighted number of tardy jobs, Journal of Scheduling, v.6 n.4, p.405-412, July/August 2003 [doi>10.1023/A:1024284828374]
• 18: Harish Patil , Robert Cohn , Mark Charney , Rajiv Kapoor , Andrew Sun , Anand Karunanidhi, Pinpointing Representative Portions of Large Intel® Itanium® Programs with Dynamic Instrumentation, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.81-92, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.28]
• 19: Maurice Queyranne, Structure of a simple scheduling polyhedron, Mathematical Programming: Series A and B, v.58 n.2, p.263-285, Feb. 2, 1993 [doi>10.1007/BF01581271]
• 20: Maurice Queyranne , Maxim Svirdenko, New and improved algorithms for minsum shop scheduling, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.871-878, January 09-11, 2000, San Francisco, California, United States
• 21: Scott Rixner , William J. Dally , Ujval J. Kapasi , Peter Mattson , John D. Owens, Memory access scheduling, Proceedings of the 27th annual international symposium on Computer architecture, p.128-138, June 2000, Vancouver, British Columbia, Canada
• 22: Thomas A. Roemer, A note on the complexity of the concurrent open shop problem, Journal of Scheduling, v.9 n.4, p.389-396, August 2006 [doi>10.1007/s10951-006-7042-y]
• 23: Andreas S. Schulz, Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds, Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.301-315, June 03-05, 1996
• 24: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 25: Standard Performance Evaluation Corporation. SPEC CPU2006. http://www.spec.org/cpu2006/.
• 26: C. S. Sung and S. H. Yoon. Minimizing Total Weighted Completion Time at a Pre-Assembly Stage Composed of Two Feeding Machines. International Journal of Production Economics, 54:247--255, 1998.
• 27: G. Wang and T. C. E. Cheng. Customer Order Scheduling to Minimize Total Weighted Completion Time. In Proc. of the 1st Multidisciplinary Conference on Scheduling Theory and Applications, pages 409--416, 2003.
• 28: L. A. Wolsey. Mixed Integer Programming Formulations for Production Planning and Scheduling Problems. In Invited talk at 12th ACM-SIAM Symposium on Mathematical Programming, 1985.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories
          Subjects: Dynamic memory (DRAM)

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

General Terms:
Algorithms, Theory

Keywords:
distributed approximation, distributed scheduling, dram memory controllers, multi-core, order scheduling