Task Orchestration : Scheduling and Mapping on Multicore Systems (D2)

Description: This module extends scheduling algorithms covered in a typical upper-level operating systems course and introduces concepts and algorithms for thread scheduling on multiprocessor systems. A priority-based algorithm for optimal throughput is presented and then modified to use power consumption as the main objective function. The notions of energy efficient computing and load balancing to improve throughput are discussed in this context. The module includes a processor-affinity-based scheduling algorithm for multicore platforms. A producer-consumer application is used as an example to illustrate the effects of thread affinity on shared-cache locality and performance. The module briefly covers simultaneous multithreading (SMT) and issues related to scheduling of hardware threads.

Recommended Length: One lecture (~1:15 min)

Recommended Course: Operating Systems

Topics and Learning outcomes (per NSF/IEEE-TCPP PDC Curriculum):

  • [Programming] Tasks and threads: understand what it means to create and assign work to threads in a parallel program and how this assignment affects performance; know how to assign work using OpenMP
  • [Programming] Synchronization: understand the need for inter-thread synchronization; be able to write shared memory programs with critical regions, producer-consumer communication, and get speedup; know the notions of mechanisms for concurrency (monitors, semaphores, etc.); understand safety considerations of parallel execution, including thread-safe functions.
  • [Programming] Load balancing: understand the effects of load imbalances on performance and power; understand ways to balance load across threads or processes
  • [Programming] Scheduling and mapping: understand how the operating system schedules threads to computation cores; understand the performance impact of such mapping

Lecture Material: [ PDF ] [ PPT ]

Sample Source Code:

  • Pthreads implementation of a producer-consumper application [ tar.gz ]

Pedagogical Notes: available for instructors only

Sample Exam Question: available for instructors only

News

Jun '15: Qasem speaks at HPC Workshop at Prairiw View A & M

Oct '14: Paper accepted at SIGCSE15

Oct '14: Short paper accepted at EduHPC14 (co-located with SC14)

Aug '14: First regional workshop held at Texas State

May '14: Call for participation in first regional workshop

Mar '14: Qasem serves as penelist in SIGCSE special session on PDC

Nov '13: Poster presented at Supercomputing conference

Sep '13: Paper accepted at EduPDHPC13

Aug '13: Qasem participates in CSinParallel Four Corners Workshop

Jul '13: Qasem receives Early Adopter grant

Mar '13: Qasem presents at NSF Showcase at SIGCSE13

Jan '13: Five new modules implemented

Aug '12: Burtscher receives Early Adopter grant

Contact

Apan Qasem (PI)
Department of Computer Science
Texas State University
601 University Dr
San Marcos, TX 78666

Office: Comal 307A
Phone: (512) 245-0347
Fax: (512) 245-8750
E-mail: apan "AT" txstate · edu