Modelling and developing co-scheduling strategies on multicore processors
On-chip cache is often shared between processes that run concurrently on different cores of the same processor. Resource contention of this type causes performance degradation to the co-running processes. Contention-aware co-scheduling refers to the class of scheduling techniques to reduce the perfo...
| Main Authors: | , , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
IEEE
2015
|
| _version_ | 1826308388317822976 |
|---|---|
| author | Zhu, H He, L Gao, B Li, K Sun, J Chen, H Li, K |
| author_facet | Zhu, H He, L Gao, B Li, K Sun, J Chen, H Li, K |
| author_sort | Zhu, H |
| collection | OXFORD |
| description | On-chip cache is often shared between processes that run concurrently on different cores of the same processor. Resource contention of this type causes performance degradation to the co-running processes. Contention-aware co-scheduling refers to the class of scheduling techniques to reduce the performance degradation. Most existing contention-aware co-schedulers only consider serial jobs. However, there often exist both parallel and serial jobs in computing systems. In this paper, the problem of co-scheduling a mix of serial and parallel jobs is modelled as an Integer Programming (IP) problem. Then the existing IP solver can be used to find the optimal co-scheduling solution that minimizes the performance degradation. However, we find that the IP-based method incurs high time overhead and can only be used to solve small-scale problems. Therefore, a graph-based method is also proposed in this paper to tackle this problem. We construct a co-scheduling graph to represent the co-scheduling problem and model the problem of finding the optimal co-scheduling solution as the problem of finding the shortest valid path in the co-scheduling graph. A heuristic A*-search algorithm (HA*) is then developed to find the near-optimal solutions efficiently. The extensive experiments have been conducted to verify the effectiveness and efficiency of the proposed methods. The experimental results show that compared with the IP-based method, HA* is able to find the near-optimal solutions with much less time. |
| first_indexed | 2024-03-07T07:18:46Z |
| format | Conference item |
| id | oxford-uuid:b1bc69ca-c60b-4361-91a5-6a7f2d78f3d1 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:18:46Z |
| publishDate | 2015 |
| publisher | IEEE |
| record_format | dspace |
| spelling | oxford-uuid:b1bc69ca-c60b-4361-91a5-6a7f2d78f3d12022-09-02T17:21:41ZModelling and developing co-scheduling strategies on multicore processorsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:b1bc69ca-c60b-4361-91a5-6a7f2d78f3d1EnglishSymplectic ElementsIEEE2015Zhu, HHe, LGao, BLi, KSun, JChen, HLi, KOn-chip cache is often shared between processes that run concurrently on different cores of the same processor. Resource contention of this type causes performance degradation to the co-running processes. Contention-aware co-scheduling refers to the class of scheduling techniques to reduce the performance degradation. Most existing contention-aware co-schedulers only consider serial jobs. However, there often exist both parallel and serial jobs in computing systems. In this paper, the problem of co-scheduling a mix of serial and parallel jobs is modelled as an Integer Programming (IP) problem. Then the existing IP solver can be used to find the optimal co-scheduling solution that minimizes the performance degradation. However, we find that the IP-based method incurs high time overhead and can only be used to solve small-scale problems. Therefore, a graph-based method is also proposed in this paper to tackle this problem. We construct a co-scheduling graph to represent the co-scheduling problem and model the problem of finding the optimal co-scheduling solution as the problem of finding the shortest valid path in the co-scheduling graph. A heuristic A*-search algorithm (HA*) is then developed to find the near-optimal solutions efficiently. The extensive experiments have been conducted to verify the effectiveness and efficiency of the proposed methods. The experimental results show that compared with the IP-based method, HA* is able to find the near-optimal solutions with much less time. |
| spellingShingle | Zhu, H He, L Gao, B Li, K Sun, J Chen, H Li, K Modelling and developing co-scheduling strategies on multicore processors |
| title | Modelling and developing co-scheduling strategies on multicore processors |
| title_full | Modelling and developing co-scheduling strategies on multicore processors |
| title_fullStr | Modelling and developing co-scheduling strategies on multicore processors |
| title_full_unstemmed | Modelling and developing co-scheduling strategies on multicore processors |
| title_short | Modelling and developing co-scheduling strategies on multicore processors |
| title_sort | modelling and developing co scheduling strategies on multicore processors |
| work_keys_str_mv | AT zhuh modellinganddevelopingcoschedulingstrategiesonmulticoreprocessors AT hel modellinganddevelopingcoschedulingstrategiesonmulticoreprocessors AT gaob modellinganddevelopingcoschedulingstrategiesonmulticoreprocessors AT lik modellinganddevelopingcoschedulingstrategiesonmulticoreprocessors AT sunj modellinganddevelopingcoschedulingstrategiesonmulticoreprocessors AT chenh modellinganddevelopingcoschedulingstrategiesonmulticoreprocessors AT lik modellinganddevelopingcoschedulingstrategiesonmulticoreprocessors |