Ignore:
Timestamp:
Sep 12, 2022, 4:35:50 PM (2 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, ast-experimental, master, pthread-emulation
Children:
fc96890
Parents:
4ab54c9
Message:

Checking conclusion

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/thierry_delisle_PhD/thesis/text/conclusion.tex

    r4ab54c9 r1c334d1  
    22
    33Building the \CFA runtime has been a challenging project.
    4 The work was divided between high-level concurrency design and a user-level threading runtime (Masters thesis), and low-level support of the user-level runtime using OS kernel-threading and its (multiple) I/O subsystems (Ph.D. thesis).
     4The work was divided between high-level concurrency design and a user-level threading runtime (Masters's thesis), and low-level support of the user-level runtime using OS kernel-threading and its (multiple) I/O subsystems (Ph.D. thesis).
    55Because I am the main developer for both components of this project, there is strong continuity across the design and implementation.
    6 This continuity provides a consistent approach to advanced control-flow and concurrency, with easier development, management and maintenance of the runtime in the future.
     6This continuity provides a consistent approach to advanced control flow and concurrency, with easier development, management and maintenance of the runtime in the future.
    77
    8 I believed my Masters work would provide the background to make the Ph.D work reasonably straightforward.
     8I believed my Masters's work would provide the background to make the Ph.D. work reasonably straightforward.
    99However, I discovered two significant challenges.
    1010
    11 First, modern symmetric multiprocessing CPU have significant performance penalties for communicationm, often cache related.
    12 A SQMS scheduler (see Section~\ref{sched}), with its \proc-shared ready-queue, has perfect load-balancing but poor affinity resulting in high communication across \procs.
    13 A MQMS scheduler, with its \proc-specific ready-queues, has poor load-balancing but perfect affinity often resulting in significantly reduced communication.
     11First, modern symmetric multiprocessing CPUs have significant performance penalties for communication, often cache-related.
     12An SQMS scheduler (see Section~\ref{sched}), with its \proc-shared ready-queue, has perfect load-balancing but poor affinity resulting in high communication across \procs.
     13An MQMS scheduler, with its \proc-specific ready-queues, has poor load-balancing but perfect affinity often resulting in significantly reduced communication.
    1414However, implementing fairness for an MQMS scheduler is difficult, since fairness requires \procs to be aware of each other's ready-queue progress, \ie communicated knowledge.
    1515For balanced workloads with little or no data sharing, \ie embarrassingly parallel, an MQMS scheduler is near optimal, \eg a state-of-the-art work-stealing scheduler.
     
    1818Several of my attempts at building a fair scheduler compared poorly to work-stealing schedulers because of the thin communication margin.
    1919
    20 Second, the kernel locking, threading, and I/O in the Linux operating system offers very little flexibility, and are not designed to facilitate user-level threading.
    21 There are multiple concurrency aspects in Linux that require carefully following a strict procedure in order to achieve acceptable performance.
     20Second, the kernel locking, threading, and I/O in the Linux operating system offer very little flexibility and are not designed to facilitate user-level threading.
     21There are multiple concurrency aspects in Linux that require carefully following a strict procedure to achieve acceptable performance.
    2222To be fair, many of these concurrency aspects were designed 30-40 years ago, when there were few multi-processor computers and concurrency knowledge was just developing.
    23 It is unfortunate that little has changed in the intervening years.
     23Unfortunately, little has changed in the intervening years.
    2424
    25 Also, my decision to use @io_uring@ was both a positive and negative.
     25Also, my decision to use @io_uring@ was both positive and negative.
    2626The positive is that @io_uring@ supports the panoply of I/O mechanisms in Linux;
    2727hence, the \CFA runtime uses one I/O mechanism to provide non-blocking I/O, rather than using @select@ to handle TTY I/O, @epoll@ to handle network I/O, and managing a thread pool to handle disk I/O.
    28 Merging all these different I/O mechanisms into a coherent scheduling implementation would require much more work than what is present in this thesis, as well as a detailed knowledge of multiple I/O mechanisms.
     28Merging all these different I/O mechanisms into a coherent scheduling implementation would require much more work than what is present in this thesis, as well as detailed knowledge of multiple I/O mechanisms.
    2929The negative is that @io_uring@ is new and developing.
    3030As a result, there is limited documentation, few places to find usage examples, and multiple errors that required workarounds.
     
    3333It does not seem to reach deep into the kernel's handling of \io, and as such it must contend with the same realities that users of @epoll@ must contend with.
    3434Specifically, in cases where @O_NONBLOCK@ behaves as desired, operations must still be retried.
    35 To preserve the illusion of asynchronicity requires delegating these operations to kernel threads.
     35Preserving the illusion of asynchronicity requires delegating these operations to kernel threads.
    3636This requirement is also true of cases where @O_NONBLOCK@ does not prevent blocking.
    37 Spinning up internal kernel threads to handle blocking scenarios is what developers already do outside of the kernel, and managing these threads adds significant burden to the system.
     37Spinning up internal kernel threads to handle blocking scenarios is what developers already do outside of the kernel, and managing these threads adds a significant burden to the system.
    3838Nonblocking I/O should not be handled in this way.
    3939
    4040\section{Goals}
    41 This work focusses on efficient and fair scheduling of the multiple CPUs, which are ubiquitous on all modern computers.
     41This work focuses on efficient and fair scheduling of the multiple CPUs, which are ubiquitous on all modern computers.
    4242The levels of indirection to the CPUs are:
    4343\begin{itemize}
     
    4949The OS and library presentation of disk and network I/O, and many secondary library routines that directly and indirectly use these mechanisms.
    5050\end{itemize}
    51 The key aspect of all of these mechanisms is that control flow can block, which immediately hinders any level above from making scheduling decision as a result.
     51The key aspect of all of these mechanisms is that control flow can block, which immediately hinders any level above from making scheduling decisions as a result.
    5252Fundamentally, scheduling needs to understand all the mechanisms used by threads that affect their state changes.
    5353
     
    6161Performance manifests in making efficient use of the underlying kernel threads that provide indirect access to the CPUs.
    6262
    63 This thesis achieves its stated contributes by presenting:
     63This thesis achieves its stated contributions by presenting:
    6464\begin{enumerate}[leftmargin=*]
    6565\item
     
    7272These core algorithms are further extended with a low-latency idle-sleep mechanism, which allows the \CFA runtime to stay viable for workloads that do not consistently saturate the system.
    7373\end{enumerate}
    74 Finally, the complete scheduler is fairly simple with low-cost execution, meaning the total cost of scheduling during thread state-changes is low.
     74Finally, the complete scheduler is fairly simple with low-cost execution, meaning the total cost of scheduling during thread state changes is low.
    7575
    7676\section{Future Work}
    77 While the \CFA runtime achieves a better compromise, in term of performance and fairness, than other schedulers, I believe further improvements can be made to reduce or eliminate the few cases where performance does deteriorate.
     77While the \CFA runtime achieves a better compromise, than other schedulers, in terms of performance and fairness, I believe further improvements can be made to reduce or eliminate the few cases where performance does deteriorate.
    7878Fundamentally, achieving performance and starvation freedom will always be goals with opposing needs even outside of scheduling algorithms.
    7979
    8080\subsection{Idle Sleep}
    81 A difficult challenge, not fully address in this thesis, is idle-sleep.
     81A difficult challenge, not fully addressed in this thesis, is idle-sleep.
    8282While a correct and somewhat low-cost idle-sleep mechanism is presented, several of the benchmarks show notable performance degradation when too few \ats are present in the system.
    8383The idle sleep mechanism could therefore benefit from a reduction of spurious cases of sleeping.
    8484Furthermore, this thesis did not present any heuristic for when \procs should be put to sleep and when \procs should be woken up.
    85 While relaxed timestamps and topology awareness made a notable improvements in performance, neither of these techniques are used for the idle-sleep mechanism.
     85While relaxed timestamps and topology awareness made notable performance improvements, neither of these techniques are used for the idle-sleep mechanism.
    8686
    87 Here are opportunities where these techniques could be use:
     87Here are opportunities where these techniques could be used:
    8888\begin{itemize}
    8989\item
     
    100100
    101101\subsection{Hardware}
    102 One challenge that needed to be overcome for this thesis is that the modern x86-64 processors has very few tools to implement fairness.
     102One challenge that needed to be overcome for this thesis is that the modern x86-64 processors have very few tools to implement fairness.
    103103\Glspl{proc} attempting to help each other inherently cause cache-coherence traffic.
    104104However, as mentioned in Section~\ref{helping}, relaxed requirements mean this traffic is not necessarily productive.
     
    111111Another option is to read multiple memory addresses and only wait for \emph{one of} these reads to retire.
    112112This approach has a similar effect, where cache lines with more traffic are waited on less often.
    113 In both of these examples, some care is needed to ensure that reads to an address \emph{sometime} retire.
     113In both of these examples, some care is needed to ensure that reads to an address \emph{sometimes} retire.
    114114
    115 Note, this idea is similar to \newterm{Hardware Transactional Memory}~\cite{wiki:htm}, which allows groups of instructions to be aborted and rolled-back if they encounter memory conflicts when being retired.
     115Note that this idea is similar to \newterm{Hardware Transactional Memory}~\cite{wiki:htm}, which allows groups of instructions to be aborted and rolled back if they encounter memory conflicts when being retired.
    116116However, I believe this feature is generally aimed at large groups of instructions.
    117117A more fine-grained approach may be more amenable by carefully picking which aspects of an algorithm require exact correctness and which do not.
Note: See TracChangeset for help on using the changeset viewer.