Context Navigation

-                      r4dba1da
+                      r0fec6c1
 Because I am the main developer for both components of this project, there is strong continuity across the design and implementation.
 This continuity provides a consistent approach to advanced control-flow and concurrency, with easier development, management and maintenance of the runtime in the future.
+I believed my Masters work would provide the background to make the Ph.D work reasonably straightforward.
+However, I discovered two significant challenges.
+I believed my Masters work would provide the background to make the Ph.D work reasonably straightforward.
+However, in doing so I discovered two expected challenges.
+First, while modern symmetric multiprocessing CPU have significant performance penalties for communicating across cores.
+This makes implementing fair schedulers notably more difficult, since fairness generally requires \procs to be aware of each other's progress.
+This challenge is made even harder when comparing against MQMS schedulers (see Section\ref{sched}) which have very little inter-\proc communication.
+This is particularly true of state-of-the-art work-stealing schedulers, which can have virtually no inter-\proc communication in some common workloads.
+This means that when adding fairness to work-stealing schedulers, extreme care must be taken to hide the communication costs so performance does not suffer.
+Second, the kernel locking, threading, and I/O in the Linux operating system offers very little flexibility of use.
+First, modern symmetric multiprocessing CPU have significant performance penalties for communication (often cache related).
+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.
+A MQMS scheduler, with its \proc-specific ready-queues, has poor load-balancing but perfect affinity often resulting in significantly reduced communication.
+However, 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.
+% This challenge is made harder when comparing against MQMS schedulers (see Section\ref{sched}) which have very little inter-\proc communication.
+For balanced workloads with little or no data sharing (embarrassingly parallel), an MQMS scheduler is near optimal, \eg state-of-the-art work-stealing schedulers.
+For these kinds of fair workloads, adding fairness must be low-cost to hide the communication costs needed for global ready-queue progress or performance suffers.
+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.
 There are multiple concurrency aspects in Linux that require carefully following a strict procedure in order to achieve acceptable performance.
 To 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.
 …
 The positive is that @io_uring@ supports the panoply of I/O mechanisms in Linux;
 hence, 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.
 Merging all these different I/O mechanisms into a coherent scheduling implementation would require a much more work than what is present in this thesis, as well as detailed knowledge of the I/O mechanisms in Linux.
+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.
 The negative is that @io_uring@ is new and developing.
 As a result, there is limited documentation, few places to find usage examples, and multiple errors that required workarounds.
 Given what I now know about @io_uring@, I would say it is insufficiently coupled with the Linux kernel to properly handle non-blocking I/O.
 It 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.
+It 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.
 Specifically, in cases where @O_NONBLOCK@ behaves as desired, operations must still be retried.
 To preserve the illusion of asynchronicity, this requires delegating operations to kernel threads.
 This is also true of cases where @O_NONBLOCK@ does not prevent blocking.
+To preserve the illusion of asynchronicity requires delegating these operations to kernel threads.
+This requirement is also true of cases where @O_NONBLOCK@ does not prevent blocking.
 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.
 Nonblocking I/O should not be handled in this way.
 …
 The OS and library presentation of disk and network I/O, and many secondary library routines that directly and indirectly use these mechanisms.
 \end{itemize}
 The key aspect of all of these mechanisms is that control flow can block, which immidiately hinders any level above from making scheduling decision as a result.
+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.
 Fundamentally, scheduling needs to understand all the mechanisms used by threads that affect their state changes.
 …
 However, direct hardware scheduling is only possible in the OS.
 Instead, this thesis is performing arms-length application scheduling of the hardware components through a set of OS interfaces that indirectly manipulate the hardware components.
 This can quickly lead to tensions if the OS interface was built with different use cases in mind.
+This can quickly lead to tensions when the OS interface has different use cases in mind.
 As \CFA aims to increase productivity and safety of C, while maintaining its performance, this places a huge burden on the \CFA runtime to achieve these goals.
 …
 These 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.
 \end{enumerate}
 Finally, the complete scheduler is fairly simple with low-cost execution, meaning the total cost of scheduling during thread state changes is low.
+Finally, the complete scheduler is fairly simple with low-cost execution, meaning the total cost of scheduling during thread state-changes is low.
 \section{Future Work}
 …
 The mechanism uses a hand-shake between notification and sleep to ensure that no \at is missed.
 \item
 The correctness of that hand-shake is critical when the last \proc goes to sleep but could be relaxed when several \procs are awake.
+The hand-shake correctness is critical when the last \proc goes to sleep but could be relaxed when several \procs are awake.
 \item
 Furthermore, organizing the sleeping \procs as a LIFO stack makes sense to keep cold \procs as cold as possible, but it might be more appropriate to attempt to keep cold CPU sockets instead.
 …
 For example, keeping a CPU socket cold might be appropriate for power consumption reasons but can affect overall memory bandwidth.
 The balance between these approaches is not obvious.
+I am aware there is a host of low-power research that could be tapped here.
 \subsection{Hardware}
 …
 If the latency is due to a recent cache invalidation, it is unlikely the timestamp is old and that helping is needed.
 As such, simply moving on without the result is likely to be acceptable.
 Another option would be to read multiple memory addresses and only wait for \emph{one of} these reads to retire.
 This approach has a similar effect, where cache-lines with more traffic would be waited on less often.
+Another option is to read multiple memory addresses and only wait for \emph{one of} these reads to retire.
+This approach has a similar effect, where cache lines with more traffic are on less often.
 In both of these examples, some care is needed to ensure that reads to an address \emph{sometime} retire.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 0fec6c1 for doc/theses/thierry_delisle_PhD/thesis/text/conclusion.tex

Legend:

doc/theses/thierry_delisle_PhD/thesis/text/conclusion.tex

Download in other formats: