서브메뉴
검색
Job Dispatching Algorithms for Handling Uncertainty and Heterogeneity in Queueing Systems
Job Dispatching Algorithms for Handling Uncertainty and Heterogeneity in Queueing Systems
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20250211152646
- ISBN
- 9798383697825
- DDC
- 621.3
- 서명/저자
- Job Dispatching Algorithms for Handling Uncertainty and Heterogeneity in Queueing Systems
- 발행사항
- [Sl] : Carnegie Mellon University, 2024
- 발행사항
- Ann Arbor : ProQuest Dissertations & Theses, 2024
- 형태사항
- 158 p
- 주기사항
- Source: Dissertations Abstracts International, Volume: 86-02, Section: B.
- 주기사항
- Advisor: Joshi, Gauri;Wang, Weina.
- 학위논문주기
- Thesis (Ph.D.)--Carnegie Mellon University, 2024.
- 초록/해제
- 요약Over the last decade, cloud computing has become ubiquitous, with applications ranging from online machine learning (ML) inferencing to hosting large files for web services. This exponential growth in cloud computing places significant demands on limited computing resources, such as GPUs, underscoring the necessity for efficiently designed systems. This thesis focuses on improving such systems using a queueing theoretic approach. Traditionally, queueing theory offers insights into understanding and improving system latency. The primary objective is to design efficient algorithms that minimize average latency-the time a job/user spends in the system-or maximize throughput-the maximum incoming traffic the system can handle.While existing literature extensively analyzes dispatching algorithms, these analyses often assume homogeneous settings that do not reflect the complexities of real-world applications. Modern systems exhibit significant heterogeneity and uncertainty in server parameters and traffic patterns. This discrepancy presents unique challenges that necessitate the development of novel solutions. We propose several approaches to address these challenges, paving the way for new directions in algorithm design and implementation.We divide the thesis into three chapters. First, we address the problem of dispatching in systems where the service rates of servers are heterogeneous and unknown. We propose a time-decaying exploratory policy that asymptotically learns the optimal policy. Second, we tackle the problem of handling traffic heterogeneity by proposing the usage of erasure-coded servers. Our analysis demonstrates that using coded servers significantly increases the throughput and drastically reduces the latency in most circumstances. Finally, we study dispatching in ML inference systems, where the challenge is to balance achieving high accuracy while experiencing low latency. Our solution includes novel algorithms that achieve the desired target accuracy while ensuring near-optimal latency.
- 일반주제명
- Electrical engineering
- 일반주제명
- Computer engineering
- 일반주제명
- Computer science
- 키워드
- Queueing theory
- 키워드
- Scheduling
- 키워드
- Machine learning
- 키워드
- Traffic patterns
- 기타저자
- Carnegie Mellon University Electrical and Computer Engineering
- 기본자료저록
- Dissertations Abstracts International. 86-02B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008250123s2024 us c eng d■001000017163270
■00520250211152646
■006m o d
■007cr#unu||||||||
■020 ▼a9798383697825
■035 ▼a(MiAaPQ)AAI31486031
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a621.3
■1001 ▼aChoudhury, Tuhinangshu.▼0(orcid)0000-0002-2893-3510
■24510▼aJob Dispatching Algorithms for Handling Uncertainty and Heterogeneity in Queueing Systems
■260 ▼a[Sl]▼bCarnegie Mellon University▼c2024
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2024
■300 ▼a158 p
■500 ▼aSource: Dissertations Abstracts International, Volume: 86-02, Section: B.
■500 ▼aAdvisor: Joshi, Gauri;Wang, Weina.
■5021 ▼aThesis (Ph.D.)--Carnegie Mellon University, 2024.
■520 ▼aOver the last decade, cloud computing has become ubiquitous, with applications ranging from online machine learning (ML) inferencing to hosting large files for web services. This exponential growth in cloud computing places significant demands on limited computing resources, such as GPUs, underscoring the necessity for efficiently designed systems. This thesis focuses on improving such systems using a queueing theoretic approach. Traditionally, queueing theory offers insights into understanding and improving system latency. The primary objective is to design efficient algorithms that minimize average latency-the time a job/user spends in the system-or maximize throughput-the maximum incoming traffic the system can handle.While existing literature extensively analyzes dispatching algorithms, these analyses often assume homogeneous settings that do not reflect the complexities of real-world applications. Modern systems exhibit significant heterogeneity and uncertainty in server parameters and traffic patterns. This discrepancy presents unique challenges that necessitate the development of novel solutions. We propose several approaches to address these challenges, paving the way for new directions in algorithm design and implementation.We divide the thesis into three chapters. First, we address the problem of dispatching in systems where the service rates of servers are heterogeneous and unknown. We propose a time-decaying exploratory policy that asymptotically learns the optimal policy. Second, we tackle the problem of handling traffic heterogeneity by proposing the usage of erasure-coded servers. Our analysis demonstrates that using coded servers significantly increases the throughput and drastically reduces the latency in most circumstances. Finally, we study dispatching in ML inference systems, where the challenge is to balance achieving high accuracy while experiencing low latency. Our solution includes novel algorithms that achieve the desired target accuracy while ensuring near-optimal latency.
■590 ▼aSchool code: 0041.
■650 4▼aElectrical engineering
■650 4▼aComputer engineering
■650 4▼aComputer science
■653 ▼aPerformance modelling
■653 ▼aQueueing theory
■653 ▼aScheduling
■653 ▼aMachine learning
■653 ▼aTraffic patterns
■690 ▼a0544
■690 ▼a0464
■690 ▼a0984
■71020▼aCarnegie Mellon University▼bElectrical and Computer Engineering.
■7730 ▼tDissertations Abstracts International▼g86-02B.
■790 ▼a0041
■791 ▼aPh.D.
■792 ▼a2024
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17163270▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
