The Martian, Computer Science, and College

This summer, the school asked professors if they would be interested in leading book discussions with incoming first-year students in Computer Science.  I, along with many other professors, volunteered, where each of us could select our specific title to discuss.  I proposed reading, The Martian, by Andy Weir.  What follows is not a review of the book, which I really enjoyed, but rather a summary of the discussion points from the hour we had together.

The following text contains many book spoilers.

We started the discussion with a short summary of my background and then a student asked about the Martian rover hacking.  It is in my opinion, plausible.  It depends on several assumptions, such as the rover's driver being able to be modified so easily to log the malformed network data (sent by the probe).  It would then be reasonable to send commands to the probe to broadcast the necessary data to construct an executable on the rover.  Then assuming that Mark can run it with sufficient privileges or that there is a known vulnerability allowing the executable to gain the privilege, the probe's data could be a patch.  Personally, I enjoyed the thought of using ASCII to communicate and myself and my TAs agree, "man ascii".  Besides, I carry an ASCII chart in my wallet.

We discussed how there was significant cooperation in solving the problems.  The crew worked together.  NASA had many teams working on the problems.  Internationally, China also provided assistance.  The people working on these problems were diverse.  And there were continual concerns about the crew's mental state and about Mark's.  Similarly, Computer Science students will need to learn to work with others, to work in groups with diverse backgrounds and skill sets, and know that there are many many more people that are wanting to see and willing to support them in having successful lives and taking steps whenever circumstances dictate.

Mark Watney survives in part by having a diverse education and training.  Being a fictional character, he has the right skills to survive, but this is based in reality.  Astronauts are trained in a diverse set of skills, particularly to maximize the value gained from their time in space.  They are not experts, but rather trained well to exercise the guidance of experts on Earth.  And similarly, I reinforced to the students that their studies should work to give them a broad foundation beyond Computer Science.

The final topic brought up by the students was about ethics.  First, should NASA tell the crew of the Hermes that Mark Watney was alive on Mars, when it was first determined.  Or instead, NASA would censor all communication to ensure that they were not informed that they abandoned Mark.  What is the trade-off between the truth and mission results?  Second, the Chinese scientists had to make a decision, is the life of one astronaut worth their probe?  Should they give up their long-prepared mission of great scientific value to instead make a "grocery delivery"?  How much is one life worth?  Third, when the Rich Purnell plan presented an alternative to rescuing Mark, was NASA obligated to consult the crew in evaluating this option?  And related, the crew of the Hermes decided to return to Mars (on the low chance of killing everyone plan) to save Mark Watney, and also extending their mission duration.  Also briefly discussed was that governments also have to decide how much a life is worth.  It is noted that the science that Mark can perform makes up for the cost of his rescue, which addresses this concern in story.

I think that the 20 or so students appreciated the hour we had together.  I hope to some day be able to meet and ultimately teach them in person.

Thesis Proposal - Lightweight Preemptable Functions

Sol Boucher presented his thesis proposal today via Zoom.  It was well attended and I think many of us are already looking forward to his defense.

Lightweight Preemptable Functions (LPF)
Function calls require some knowledge of the cost for a program to know whether it can invoke it or not in other time critical execution.

In the current space of multitasking, three approaches will be first reviewed: futures, threads, and processes.  Futures rely on the runtime to provide asynchronous execution, but preemption requires yield points, and not all execution can support these points, nor can it be clear what this future will do.  With threads, execution is fairly independent, but minimal information is provided toward scheduling and cancellation is hard.  Processes provide good support for cancellation, except that on fork(), only one thread is required to be carried over in the new process.  The other threads are canceled, which can result in inconsistent state.

The thesis proposal is: Introducing a novel abstraction for preemption at the granularity of a synchronous function call, which includes a timeout.

launch(function, timeout, argument) returning a continuation.  If the timeout elapses, the continuation is returned, but it is then the choice of the caller for whether to resume it or cancel.  This LPF executes within the same thread context as the caller, thereby reducing overhead.  However, to resume the LPF, it will need a new stack.  To support the timeout, it relies on a timer signal that can occur every ~5 microseconds.  Launch / resume have overhead comparable to this, significantly better than fork or pthread_create.  However, cancel is extremely expensive.

LPFs also have an issue with calling functions that are non-reentrant, similar to the rules governing signal handlers.  To address this, the runtime provides selective relinking to capture what the LPF is calling via the global offset table (GOT).  Some GOT entries point to dynamic libraries, other entries are initially pointing to the dynamic linker.  This runtime support also needs to intercept thread local variables.  This interception support imposes about 10ns of  overhead, which is little above the cost of function calls themselves.

Microservice approaches have significant latency, often tends to hundreds of microseconds.  Primarily the requirement to create a sufficient container, often via processes or virtualization.  If the microservice was instead written safely and using LPFs, then the latency could be reduced toward the hardware bound as measured by communicating between VMs or committing transactions.

Cancellation cleanup is difficult in languages, such as C, that require explicit cleanup.  In other languages, adding a new exception path for timeout and cancellation could then invoke the necessary destructors.  Nonetheless, this can be expensive (perhaps single milliseconds).

Other possible future work:
Another cancellation step is the cost of unloading the mirrored library, so could the runtime instead track the changes made and then determine whether to roll back or discard.
Is it possible to reduce the overhead of the preemption signals or improving their granularity.

Conference Attendance - MICRO 52 - Day 2/3

This is a rough writing of the notes from the other two keynotes.

Keynote Bill Dally on Domain-Specific Accelerators

Moore's Law is over.  Sequential performance is increasing at 3% per year.  And cost per transistor is steady or increasing.

Most of power is spent moving data around, so simple ISAs such as RISC are actually inefficient power-wise versus specialized operations.  With special data types and operations, the hardware can be designed so that something taking 10s to 100s of cycles is done in 1.  Memory bandwidth can bottleneck, as "bits are bits".

Genome matching, via Smith-Waterman algorithm, can be done in single cycle for many bases (10), while a CPU would be 35 ALU ops and 15 load/store.  And the specialized hardware is 3.1pJ (10% is memory) and the CPU is 81nJ.

Communication is expensive in power, so be small, be local.  5pJ/word for L1, 50pJ/word for LLC, and 640pJ/word for DRAM.  And most of this power is driving the wires.

Conventionally, sparse matrices need <1% set bits to be worth using due the overhead of pointers, etc.  However, special purpose hardware can overcome this overhead.

Tensor core performs D = AB + C, so how to execute this in an instruction.  For a GPU, 30pJ to fetch / decode / operand fetch the instruction.  So specialized instructions can then operate as efficiently as specialized hardware, but with that overhead.  On a GPU that power is ~20% overhead.

Keynote: An Invisible Woman: The Inside Story Behind the VLSI Microelectronic Computing Revolution in Silicon Valley

Conjecture: Almost all people are blind to innovations, especially ones by 'others' whom they did not expect to make innovations.  ('others' = 'almost all people')

Basically, we rarely notice any innovation, so they are ascribed to the perceived likely cause (c.f., the Matthew effect or the Matilda effect).  Credit for innovations is highly visible, and many awards are ascribed to people with certain reputations rather than the specific innovator.

Conference Attendance - MICRO 52 - Day 1

I am in Columbus Ohio for MICRO 52.  A third of the attendees drove from other "midwestern" universities, of which I am one. 

Keynote: Rejuvenating Computer Architecture Research with Open-Source Hardware

Moore's Law is irrelevant now, as the cost per transistor has held steady since the 28mm technology node.  The cost of any deployment depends on the development cost and only at very large scales, is the cost per transistor dominant.  Given that, how can we reduce the cost of hardware development.

Cambrian explosion of (RISC) ISAs in mid-1980s on with a great diversity of ISAs being created and competing.  Then the Intel Pentium came out, which combined the CISC ISA with a translation into the RISC micro ops.  This extinction event destroyed most of those ISAs.

Why does the instruction set architecture (ISA) matter?  It is the dominant interface in the system, defining the interaction between software and hardware.  But ISAs are currently proprietary, and tied to the fortunes of the company.  Many ISAs have come and gone.  And then each SoC (system on a chip) gets custom ISAs for each accelerator.

So there is now the RISC-V ISA that is open for use and development (which I wrote about here).  The RISC-V foundation was formed in 2015 to be the neutral guardian of the specification and formal model.  Based on this specification, there are both open-source and commercial implementations of the hardware as well as the software ecosystem.

ComputeDRAM: In-Memory Compute Using Off-the-Shelf DRAMsDRAM is designed based on commands being sent in a specific order with appropriate timings.  The oddity is that if specific commands and timings are used that violate the normal usage, then the DRAM module can perform certain operations, such as AND and OR using three specially prepared rows (source x2 and destination).

Hybrid Skiplist: Combining the Best of Near-Data-Processing and Lock-Free Algorithms

This is a student research competition work that I want to highlight.  The work is taking skip-lists, a multi-level linked list to support more efficient traversals, which has been implemented on both near-data processing (NDP) systems as well as lock-free.  The performance of the two implementations is comparable, but we should be able to do better.  The observation is that lock-free gains by having the long, frequently-accessed links in the cache, while NDP gets the data items close.  Therefore, let's combine the two approaches so the algorithm uses the lock-free approach on the long links, and leaves the rest in NDP.  A dynamic approach then adapts which nodes are in the long list and promotes them, while demoting less frequently accessed elements.

Applying Deep Learning to the Cache Replacement ProblemLet's apply machine learning to cache replacement.  Offline, a ML model can perform better than the best replacement schemes, but offline this requires lots of space, more than the cache itself.  Current algorithms (such as Hawkeye) use just the current PC, whereas the observation is that the machine learning model includes history, so perhaps history can have value.  Using this, they analyzed the history further to notice that this history information is not complete nor does it have to be ordered.  If it does not need to be ordered, then the history is a feature list (i.e., bitvector) and not a full list, so the history feature gives an index into a table of predictors for whether a line is cache friendly in usage.

NVBit: A Dynamic Binary Instrumentation Framework for NVIDIA GPUs

This is a release of a Pin-like tool, but for GPUs.  Using the framework, you can write specific instrumentation to be applied to CUDA kernels.  The framework does an analysis of the kernel to find the specific instrumentation points and then recompile / JIT the code to integrate the request types into the kernel without requiring the actual source code for the kernel.  Such types as the specific instructions executed as counts or traces.  And thereby build a simulator or error checker.

Repost: Active Learning is Better even if Students Don't Like It

Active learning is a set of techniques that require the student to take an active role in their learning during lecture.   Research strongly supports that students will learn more when the lecture utilizes these techniques.  And I have measured this effect in my own courses.  However, this research shows that students like lectures that use these techniques less even though they are learning more.  And I have also informally measured this, such as students who say at the end of the first lecture, "If you are going to require me to participate in lecture, I will not return".  Unfortunately, the present educational model is based on the student evaluations (primarily measuring what students like) to evaluate the quality of instruction.  Therefore perversely, this aggregate model encourages suboptimal teaching and learning.

The paper recommends then that professors take time in the beginning of the semester to demonstrate the benefits and gain buy in from the students.  And then continue to do so.  Students want to learn, so they will support this pedagogy.  And many students will recognize the value with time, if they give it.

Thesis Proposal: Theoretical Foundations for Modern Multiprocessor Hardware

Naama Ben-David gave her proposal this morning on Theoretical Foundations for Modern Multiprocessor Hardware.

Is there a theoretical foundation for why exponential backoff is a good design?  Exponential backoff is a practically developed algorithm that 0.

To develop such a foundation, we need to a model of time; however, requests are asynchronous and not according to a single time source.  To address this, model time with adversarial scheduling.  Thus when performing a request, there are three sources of delay:

• self-delay: backoff, sleep, local computation
• system-delay: interrupts, context switches
• contention-delay: delay caused by contention

Given this model, the adversary can, to a limited degree, decide when requests that an entity's request have passed from self-delay into the system delay can then move to contention-delay and ultimately be completed.

In BBlelloch'17, this model was applied and the work measured for different approaches.

• With no backoff, there is omega(n³) work.
• Exp backoff reduces to theta(n² log n) bound on work
• The paper also proposes a new algorithm that has high probability of O(n²)

The second phase of work is developing simple and efficient algorithms for systems that have non-volatile memory (NVRAM).  With NVRAM, on a crash or system failure, the contents in memory persist across reboot (or other restore).  This permits the system to restore the running program(s) to a finer degree than happens from auto-saves or other current techniques.  However, systems also have caches, which are not persistent.  Caches are presently managed by hardware and make decisions as to when to write contents back to memory.  Algorithms must work with the caches to ensure that results are safely in memory at selected points of execution.  There are a variety of approaches for how to select these points.

The third phase of work is modeling RDMA (remote direct memory access) systems.  Can there be a model of the different parts of such a system: memory, NIC (network interface card), and CPU?  Then explore the contention as well as possible failures in the system.

One scheme is for every processes to also be able to send messages on behalf of its shared memory neighbors, so that even if a process fails, its ability to participate in algorithms, such as consensus, is still possible.

Being a proposal, ongoing work will work on instantiations of these algorithms to measure the practical performance.

Presentation: The Quest for Energy Proportionality in Mobile & Embedded Systems

This is a summary of the presentation on "The Quest for Energy Proportionality in Mobile & Embedded Systems" by Lin Zhong.

We want mobile and other systems to be energy efficient, and particularly use energy in proportion to the intensity of the required operation.  However, processor architectures only have limited regions where these are in proportion, given certain physical and engineering constraints on the design.  ARM's big.LITTLE gives the a greater range in efficiency by placing two similar cores onto the same chip; however, it is constrained by a need to ensure the cores remain cache coherent.

The recent TI SoC boards also contained another ARM core, running the Thumb ISA for energy efficiency.  This additional core was hidden behind a TI driver (originally to support MP3 playing), but was recently exposed, so allowing further design to utilize it as part of computation.  But this core is not cache coherent with the other, main core on the board.

So Linux was extended to be deployed onto both cores (compiled for the different ISAs), while maintaining the data structures, etc in the common, shared memory space.  Then the application can run and migrate between the cores, based on application hints as to the required intensity of operations.  With migration, one of the core domains is put to sleep and releases the memory to the other core.  This design avoids synchronization between the two domains, which simplifies the code and the concurrency demands are low in the mobile space.  And here was a rare demonstration of software-managed cache coherence.

Therefore, DVFS provides about a 4x change in power, then big.LITTLE has another 5x.  The hidden Thumb core supports an additional 10x reduction in power for those low intensity tasks, such as mobile sensing.  Thus together, this covers a significant part of the energy / computation space.

However, this does not cover the entire space of computation.  At the lowest space, there is still an energy intensive ADC component (analog digital conversion).  This component is the equivalent of tens of thousands of gates.  However, for many computations, they could be pushed into the analog space, which saves on power by computing a simpler result for digital consumption and that the computation can be performed on lower quality input (tolerating noise), which reduces the energy demand.

Repost: Code Smells ... Is concurrency natural?

Writing parallel code is not considered easy, but it can be a natural approach to some problems for novices.  When a beginner wants something to happen twice concurrently, the reasonable thing would be to do what works once, a second time.  Instead, this may conflict with other constructs of the language, such as main() or having to create threads.  See more here.

Talk: Concurrent Data Structures for Non-Volatile Memory

Today, Michal Friedman, gave a talk on Concurrent Data Structures for Non-Volatile Memory.

Future systems will contain non-volatile memory.  This is memory that exhibits normal DRAM characteristics, but can maintain its contents even across power failures.  In current systems, caches update memory on either evictions and flushes.  Flushes, however, impose overhead due to the memory access time and overriding the write-back nature of most caches.

Linearizability is one definition for concurrency governing the observation of the operations.  This can be extended to durable linearizability being on a durable system, such that data is flushed before global visibility (initialization), flush prior operations (dependence), and persist operations before they complete (completion).  But a further extension is required to know when a sequence of operations are complete, beyond just taking snapshots of the memory state.

Relaxed, durable, and log versions of lock-free queue that extend Michael and Scott's baseline queue implementation.  Each version provides stronger guarantees: relaxed are the existing augmented with a sync operation to snapshot state, durable preserves the data structure across failures, log identifies the specific state.  The main guarantee is that the data structure will be consistent for any set of thread crashes, which is stronger than the lock-free guarantee.

We do this by extending the prior lock-free versions that include memory flushes of key state, and that later update which see volatile state will flush that state before completing their operations.  This meets the durable linearizability.  And can be extended by also have a log of operations that are updated and maintained before the operations themselves execute.  These logs are per-thread, so as to be unordered and to be individually stateful.

The relaxed version implements sync by creating a special object that indicates a snapshot is occurring.  If other concurrent operations find this object, they take over the snapshot and continue persisting the state before completing its own operation.  Thus a snapshot does not block other operations, but still occurs at that point in the sequence of operations.

Based on performance measurements, the relaxed performs similar to the baseline implementation, while the durable and log-based implementations run slower than the relaxed but with similar performance.

Finally, TSO provides us a guarantee that the stores will reach the cache line in a desired order and not require flushing between writes.

Conference Attendance - SIGCSE 2019 - Day 2.5

Continuing at SIGCSE, here are several more paper talks that I attended on Friday.  Most of the value at SIGCSE comes from the friendly conversations with other attendees.  From 5-11p, I was in the hotel lobby talking with faculty and students.  Discussing research ideas, telling our stories from teaching, and generally renewing friendships within the field.

On the Effect of Question Ordering on Performance and Confidence in Computer Science Examinations
On the exams, students were offered a bonus if they could predict their score by within 10%.  Does the order of questions (easy -> hard, or hard -> easy) have any impact on their estimated or actual performance on an exam.  Students overpredicted by over 10% on the exams.  As a whole, the hard to easy students did worse, but this result was not statistically significant.  A small improvement is gained for women when the exams start with the hardest problem.

I wonder about whether students were biased in their prediction based on the reward.  Ultimately, the authors gave the reward to all students regardless of the quality of their prediction.

The Relationship between Prerequisite Proficiency and Student Performance in an Upper-Division Computing Course

We have prerequisites to ensure that students are prepared for the later course, an upper-level data structures class.  Students started on average with 57% of expected prerequisite knowledge, and will finish the course with an improvement of 8% on this knowledge.  There is a correlation between prerequisite score and their final score.  With several prerequisites, some knowledge concepts has greater correlation than others.  Assembly is a surprising example of a concept that relates.  Students benefit from intervention that addresses these deficiencies early in the term.

Afterward, we discussed that this work did not explore what prerequisite knowledge weakly correlated with student learning.  How might we better understand what prerequisites actually support the learning in a course?  Furthermore, can we better understand the general background of students in the course, such as class standing or general experience?

Visualizing Classic Synchronization Problems

For three classic synchronization problems: dining philosophers, bounded producer-consumer, and readers and writers.  Each one has a window displaying the operations, as well as multiple algorithmic strategies.  With these visualizations, do students learn better and also find them more engaging than reading about the problems in the textbook.  While not statistically significant, the control group exhibited better recall, although the visualization group had higher engagement.  That said, the control group exhibited higher course grades, so the difference in learning may actually be from unrelated factors.

Conference Attendance: SIGCSE 2019 - Day 1.5

Back at SIGCSE again, this one the 50th to be held.  Much of my time is spent dashing about and renewing friendships.  That said, I made it to several sessions.  I've included at least one author and linked to their paper.

Starting on day 2, we begin with the Keynote from Mark Guzdial

"The study of computers and all the phenomena associated with them." (Perlis, Newell, and Simon, 1967).  The early uses of Computer Science were proposing its inclusion in education to support all of education (1960s).  For example, given the equation "x = x0 + v*t + 1/2 a * t^2", we can also teach it as a algorithm / program.  The program then shows the causal relation of the components.  Benefiting the learning of other fields by integrating computer science.

Do we have computing for all?  Most high school students have no access, nor do they even take the classes when they do.

Computing is a 21st century literacy.  What is the core literacy that everyone needs?  C.f. K-8 Learning Trajectories Derived from Research Literature: Sequence, Repetition, Conditionals.  Our goal is not teaching Computer Science, but rather supporting learning.

For example, let's learn about acoustics.  Mark explains the straight physics.  Then he brings up a program (in a block-based language) that can display the sound reaching the microphone.  So the learning came from the program, demonstration, and prediction.  Not from writing and understanding the code itself.  Taking data and helping build narratives.

We need to build more, try more, and innovate.  To meet our mission, "to provide a global forum for educators to discuss research and practice related to the learning and teaching of computing at all levels."

Now for the papers from day 1:

Lisa Yan - The PyramidSnapshot Challenge

The core problem is that we only view student work by the completed snapshots.  Extended Eclipse with a plugin to record every compilation, giving 130,000 snapshots from 2600 students.  Into those snapshots, they needed to develop an automated approach to classifying the intermediate snapshots.  Tried autograders and abstract syntax trees, but those could not capture the full space.  But!  The output is an image, so why not try using image classification.  Of the 138531 snapshots, they generated 27220 images.  Lisa then manually labeled 12000 of those images, into 16 labels that are effectively four milestones in development.  Then, a neural network classifier classified the images.  Plot the milestones using a spectrum of colors (blue being start, red being perfect).  Good students quickly reach the complete milestones.  Struggling students are often in early debugging stages.  Tinkering students (~73 percentile on exams) take a lot of time, but mostly spend it on later milestones.  From these, we can review assignments and whether students are in the declared milestones, or if other assignment structure is required.

For the following three papers, I served as the session chair.

Tyler Greer - On the Effects of Active Learning Environments in Computing Education

Replication study on the impact of using an active learning classroom versus traditional room.  Using the same instructor to teach the same course, but using different classrooms and lecture styles (traditional versus peer instruction).  The most significant factor was the use of active learning versus traditional, with no clear impact from the type of room used.

Yayjin Ham, Brandon Myers - Supporting Guided Inquiry with Cooperative Learning in Computer Organization

Taking a computer organization course with peer instruction and guided inquiry, can the peer instruction be traded for cooperative learning to emphasize further engagement and learning.  Exploration of a model (program, documentation), then concept invention (building an understanding), then application (apply the learned concepts to a new problem).  Reflect on the learning at the end of each "lecture".  In back-to-back semesters, measure the learning gains from this intervention, as well as survey on other secondary items (such as, engagement and peer support).  However, the students in the intervention group did worse, most of which is controlled by the prior GPA.  And across the other survey points, students in the intervention group rated lower.  The materials used are available online.

Aman, et al - POGIL in Computer Science: Faculty Motivation and Challenges

Faculty try implementing POGIL in the classroom.  Start with training, then implementing in the classroom, and continued innovation.  Faculty want to see more motivation, retaining the material, and staying in the course (as well as in the program).  Students have a mismatch between their learning and their perceived learning.  There are many challenges and concerns from faculty about the costs of adoption.

Seminar Talk: Computer Science Pedagogy - Miranda Parker

This week I have been co-hosting Miranda Parker, from Georgia Tech, as part of our Colloquium on Computer Science Pedagogy.  Her work is titled, Barriers to Computing: What Prevents CS for All.

The question is what are the barriers to accessing Computer Science at the high school level.  Nation-wide, ~35% of high schools offer at least one CS course, although this is self-reported CS.  In Indiana, the most popular courses are taken by ~5000 students, state-wide.  In Austin Texas, about 6000 students take at least one CS course, out of ~110,000.

How do we know if students are successful (i.e., did they learn)?

For this, we need a validated assessment to ensure that we are measuring what we want to measure.  An initial assessment, FCS1, worked fairly well and across multiple introductory programming languages; however, the assessment had limits in its use, which lead to the SCS1.  This assessment correlated well with FCS1, so it can standin; however, it was an hour long.  Assessments should: cover the content, vary in difficulty, and have good discrimination (so individual scores are good predictors for the overall performance).  In analysis, most of the SCS1 questions were hard, and few provided good discrimination.  The assessment was then adapted to focus on the medium difficulty problems that discriminate (in test scores), and expanded to a 30 minute test.

With a measurement of whether students are succeeding in Computer Science, we can walk back to investigate what things influence students to succeed in Computer Science.

Among prior studying factors, we know that students do better in CS if they have more prior experience with Computer Science, and students do better in CS (as well as STEM and general education) with higher socioeconomic status (SES).  There are also known prior links between SES and access to computing (whether it is formal courses, or informally), and SES to spatial reasoning.  And both of these later components are linked to CS achievement.

In exploratory study (large, public university with mainly high SES students), showed statistical correlation from spatial reasoning to CS achievement.  There was not correlation from having access to achievement.  In the interest of time, this point was not presented further.

Barriers to computing

There are three main sources of access to Computer Science courses: state policies, geography (such as, circumstances, industry, or neighboring schools with CS), and resources (such as, time and money or rural versus urban).

In partnership with Georgia Department of Education, CS enrollment data from 2012-2016, plus other public data (such as, characteristics of the county and of the school), for each of the 181 school districts in Georgia, where each district has at least one high school.  Using the definition of CS courses, being those that count toward the graduation requirement in Georgia as computer science, versus other computing courses, such as web design or proficiency with office.  In Georgia, out of 500,000 students, about 6000 took a CS course in a given year, where about 50% of schools offered computer science during at least one year in that time frame.  And the 6000 students are actually student course events, where a student taking two CS courses would count twice.

For those schools, CS enrollment, total high school enrollment, and median income contribute to whether CS will be offered in the next year.

This work is yet ongoing, where the next steps are to visit schools and collect further data on these factors, such as why a school discontinued a course offering, or now offers one.  Or what do students these courses go on to do?  An audience question wondered whether the CS courses offered relates to the courses offered of other parts of STEM.

Thesis Defense: Practical Concurrency Testing

Ben Blum defended his dissertation work today on Practical Concurrency Testing.  What follows are the notes from that defense.

To prove that a program is correct across arbitrary concurrency.  There are three testing approaches:
unit testing of the most likely, stress testing that is not systematic, and verification that requires separate tools and techniques to describe.

Landslide is a proposed technique that is based on Stateless Model Checking (Godefroid '97), which tests a different execution interleaving on every iteration.  However, the naive interleaving provides O(2^n) states to test.  [Flanagan '05] identified equivalent interleavings and [Musuvathi '08] proposed heuristic orderings to identify the possible bugs faster.  This approach can often require annotations, so adoption requires automated instrumentation.  This space is addressing further concurrency problems such as weak memory models, but hardware transactional memory is still open.

This instrumentation requires preemption points.  Finer-grained finds more bugs, but increases the states to test.  Bugs / failures follow certain cases, such as use-after-free, deadlocks, assertion failures, and invalid memory accesses.  Dynamic data-race analysis can help inform the necessary preemption points.

As a reminder, a data race:
- one or more accesses is write
- threads are not holding the same mutex
- Nor is there other ordering requirements (condition variable, etc)

Quicksand applies this analysis to select different smaller problem spaces using subsets of possible preemption points.  Each subset also represents smaller parts of the larger possible problem space.  If these subsets are all satisfied, then represents a full verification of the program.  Prior work explored using APIs such as mutex_lock/unlock, or using every shared variable access as preemption points.

This tester is deployed in OS courses at CMU, PSU, and U Chicago.  Manual annotation is not viable for students, especially those struggling for whom the traces would be valuable.  That said, students regularly deploy ad-hoc synchronization, such as while (!ready) yield();, requires heuristics as the naive model checking must test every possible count of yielding and its interleaving.

When used by students, about 75% of tested kernels / libraries have identifiable bugs from the testing framework.  For the tested submissions (7 semesters) of students at CMU, there is an improvement in grades, but it is not statistically significant when correcting for the opt-in bias.  Most students are then able to fix their bugs found by the tool.

Hardware transactional memory poses a separate challenge for model checking.  Aborted transactions are observationally equivalent to an immediately failed transaction.  Furthermore, all transactions must be assumed to abortable, as there are many possible causes of aborts.  As prior posts covered, this fact requires that any transaction have a valid abort path.  And this abort path requires most of the verification.

Testing Landslide using hand-written tests, transactional data structures, and a TSX-based spinlock.  Each set of tests has a concurrency or performance bug in the implementations.  What about demonstrating that there are no bugs in implementation?  With 10 hours of CPU time, verification is only possible for small cases on complex code.  That said, practical testing so far only requires <4 preemptions to create the buggy scenario.  There can be other bugs requiring an increasingly complex ordering, but generally those are very rare.

Abstraction reduction [Simsa '13], works to reduce primitives within implementations to verified components, such as mutual exclusion, etc.  Using this technique then allows Landslide to verify the complex HTM implementations at higher thread counts.

In attendance are the recent instructors of Operating Systems and the TAs.

NASA Talk: Making Miracles Happen

Dr. Thomas H. Zurbuchen the Associate Administrator of NASA's Science Mission Directorate gave a talk today about some key lessons he has learned and observed from his years with NASA, as well as years before.  The following is my quick notes from his talk.

Planning for the future, Voyager launched with the plan to visit Jupiter and Saturn.  But the scientists still had plans for the possibility to visit Uranus and Neptune based on that launch window.  And also, that in the lifetime of the probes, they may leave the Heliosphere.  Imagine that over 40 years after launch, there are still papers to be written in Nature or Science from the mission.  Voyager 2 is nearing this mark, which Voyager 1 already crossed.

Solar probe problem was to explore near to the Sun.  The desire was there from 60 years ago.  And eventually from decades of other work, the technology was there to support components such as solar panels that can operate close to Sun.  Once the technology was available, the proposal was based on a $4 billion probe, which was outside the budget.  But NASA offered to design / launch for $1 billion.  This forced a complete redesign.  The original mission used a single Jupiter flyby to bring the probe to 4 solar radii.  For $1 billion, the flight path would instead use Venus to do repeated flybys and eventually lower the perihelion to 9 solar radii.  While 9 > 4, the Venus flight path provides many flybys of the Sun, which provides a richer dataset from each flyby.  This probe is the Parker Solar Probe, also exceptionally named for the still living scientist Eugene Parker.

Cassini reinforced the need for teams to have diverse backgrounds and training.  That greater success is possible from having the great teams.

Hubble provided the research, just last year alone, for ~1000 publications.  On the initial launch, there was the well known flaw in the mirror, when NASA had been predicting great images.  After studying the results, a tech worked out that the mirror was slightly out of position, and by a small shift of the sensor, everything worked.

Shortly after finishing his PhD, Dr. Z came up with a new sensor in '98 to be possibly part of Messenger, at its launch in 2004, which was multiple times added and removed from the craft.  And even after the launch, it took Messenger 7 years to complete the orbital path and remove sufficient energy so that the probe could enter orbit of Mercury.  This requires patience.

When working in teams, he tells about being the Swiss army.  Barbed wire had to be placed around the camp.  This was the job given to those in trouble.  But he talked with them on this duty and helped.  So eventually, rather than just being the trouble job, the team was a good team, and some soldiers wanted to work on those teams.  Better to be on a good team doing a bad task, than a bad team doing a good task.

The National Academy of Science sets the science priorities (this process from priority to mission I read significantly about in Chasing New Horizons), but ultimately the specific mission to meet the science priority is decided by Dr. Z.  Then that mission moves through multiple steps and reviews.  And one of the key steps is that while Dr. Z makes the decision, these decisions are based on the good advice from the experts.

For the missions flown, Dr. Z has about 5 failures for every success.  These failures are things like being removed from the program or the mission being canceled.  And sometimes it is for technical failures of the device or the probe.  Things will fail.  At every launch, he goes there to watch and has a large mission plan.  Most of that mission plan covers what to do if things go wrong.  Plan for the failure.

Is C low level?

A recent ACM article, C is Not a Low-Level Language, argues that for all of our impressions that C is close to hardware, it is not actually "low-level".  The argument is as follows, C was written for the PDP-11 architecture and at the time, it was a low-level language.  As architectures have evolved, C's machine model has diverged from hardware, which has forced processor design to add new features to attain good performance with C, such as superscalar for ILP and extensive branch prediction. 
Processors must also maintain caches to hide the memory latency, which require significant logic to maintain coherence and the illusion that the memory is shared between the threads of a process.  Furthermore, the compiler is also called upon to find optimization opportunities that may be unsound and definitely require programmer years to implement.

The author repeatedly contrasts with GPUs, while noting that they require very specific problems, or "at the expense of requiring explicitly parallel programs".  If you were not keeping track, a GPU requires thousands of threads to match the CPU's performance. The author calls for, "A processor designed purely for speed, not for a compromise between speed and C support, would likely support large numbers of threads, have wide vector units, and have a much simpler memory model."  Which generally sounds like the GPU design.

I appreciate the callouts to C's shortcomings, which it certainly has.  The notion that C has driven processor design is odd, yet it does reflect the fact that processors are designed to run current programs fast.  And with the programs being written in either C or a language built on C, that forces many programs into particular patterns.  I even spent some time in my PhD studies considering a version of this problem: how do you design a new "widget" for the architecture if no programs are designed for widgets to be available?

All to say, I think C is a low-level language, and while its distance from hardware may be growing, there is nothing else beneath it.  This is a gap that needs to be addressed, and by a language that has explicit parallel support.

Thesis Defense: Responsive Parallel Computation

We can consider parallelism strategies as either competitive (such as pthreads) or cooperative (such as Cilk).  Cooperative systems assume that the parallel computation is being equally distributed across the threads, such that other tasks are not prioritized.

Into this, Stefan Muller presented a Responsive Parallel Computation approach where the two models can be unified.  Or put another way, "We can extend existing cooperative language and cost models to account for competitive threading constructs, and to design and implement efficient and responsive scheduling algorithms."

Cooperative systems, such as Cilk, rely on task queues and work stealing to implement the parallelism, but when IO is involved, the common implementations use blocking system calls.  In the cooperative system, this blocking call then blocks one of the worker threads, rather than just the working task.

For operating system scheduling, there are many threads within the myriad of processes in the system that may need to run.  The OS often uses a priority associated with any thread / process to determine these scheduling decisions.  When programmers assign priorities (if they do at all), they often are trying to express a relative ordering between different tasks rather than absolute priorities.  As some systems limit priorities to a handful to as many as 100, the mapping of priority classes to numeric levels can be unclear.

Propose an extension to ML, PriML, with two new types:
t cmd[p] - command p returning t
t thread[p] - thread at priority p returning t

priority and order declarations enable defining the priority and the specifying the partial order between those priorities.  spawn[priority] {expression} to create the thread.  sync to retrieve the result.  Or poll to return an option that can be matched, so that we can select from multiple threads.  For example, the following PriML sequence spawns two threads to sort emails with different methods and selects the faster one.

t1 <- spawn[p] {do (qsort date emails)};
t2 <- spawn[p] {do (mergesort date emails)};
do (let fun choose () =
  cmd[p]
  {
    v1 <- poll t1;
    v2 <- poll t2;
    do (case (v1, v2) of
      (SOME l, _) =>
        cmd[p] {cancel t2; ret l}
      | (_, SOME l) =>
        cmd[p] {cancel t1; ret l}
      | (NONE, NONE) => choose ())
    }
  in
    choose ()
  end)

These features then allow the language to enforce the priority constraints, and avoid any priority inversion, as sync must always be to an equal or higher priority, and poll can be to any.

Returning to parallel program analysis, we represent them with DAGs; however, the DAG must be extended with priority annotations and the work / span calculations.  This analysis can explore different schedules, such that adding fairness for all thread priorities would extend the bound on time.

Book Review: Valley of Genius

Valley of Genius is a history of Silicon Valley based on the people who made it.  Since the work was based on interviews, I expected that it would read as actual interviews, where the dialog exists between the author and the "genius".  Instead, the author was removed from the chapters and instead the entire text consisted of the different participants being quoted.  This writing style took sometime to accept.  Initially, I wanted to know exactly who each person was and their role in the narration, which given the numbers involved would significantly detract from the story being told.  Then I stopped bothering with the names, only looking for them when two (or more) speakers refer to each other.  And this aspect is the best of the book, to have the different individuals having a debate in the dialog, otherwise each chapter is just narration.  That said, the concern is that there is lost context to the quotes, as the author has explicitly stated the interviews had been spliced together.

All in all I enjoyed the book, but that only merits 3.5/5 stars.

(A free copy of the book was provided through Goodreads.)

Repost: CRA Memo on Best Practices for Engaging Teaching Faculty in Research Computing Departments

Mark Guzdial noted today that the CRA has prepared its memo about teaching faculty in research departments.  For the past two years, I have been going to a CRA event at SIGCSE geared toward preparing this memo, so good to see its release.  I am thankful that at my institution, we have most of the things outlined in the memo and are treated roughly as equals to the tenure-track faculty.

Book Review: The Art of Application Performance Testing

The Art of Application Performance Testing, covers what it says.  The book starts with concepts general to any performance testing, which was interesting to me.  Most of the text focuses though on the Application part of the title.  The applications here are primarily web-based, or other client-server based setups, and not just the generic "application" referring to any program.  That said, I do not work on such applications, so the remainder of the text was of less value to me.

In testing applications, a performance analyst needs to establish a representative workload, which includes the actions to perform, and the combined load.  For example, most users logging in to their bank will view their account balance, while others might transfer money or pay a bill.  Combined these actions might represent most of the work from users.  Then for each unit of server, how many users should be able to perform a mix of those actions, which forms the load.

After establishing the workload, the analyst needs to implement the described workload, which requires a tool that generates the load (either by driving the application itself or replaying a synthetic trace of the load).  For those tools, what additional hardware is required to deploy this load?  Does the deployment take into account geographic and other user variations (so that the load generation is representative of the user base)?  Finally, what tooling and methodology exists for profiling and recording the execution of the workload for present and future analysis?

So I appreciated the content of the book and would recommend it to individuals focusing on testing of user-facing applications.

Review: Lessons from Building Static Analysis Tools at Google

The Communications of the ACM recently had several development articles, and I found the one on static analysis tools at Google particularly interesting.  The article works through how Google went about integrating static analysis tools into every developer's workflow.  And the tools have to be in the workflow, or developers will "forget" to use them.  The second problem with the tools is ensuring that the feedback is useful.  Currently, each dev will mark the items as either useful or incorrect.  If a tool exceeds a 10% false-positive rate, it is temporarily disabled until that tool's developers can fix the flagged issues.  The third issue with the tools is that some are expensive.  Depending on the type of static analysis, the time required may be significant.  Thus the tools are classified into two camps: on each compile, or on each code review / commit.  It is also important that some tools can be temporarily disabled, such that during debugging or refactoring the code may temporarily mutate into an "unsafe" state to simplify the process.

Personally, I am glad that they are integrating analysis tools into the development workflow.  Much work has been done to find bugs and issues within source code, so it is good that these analyses can be utilized regularly to improve code quality.

(As a note, I do not nor never have worked for Google, so I can only write based on the ACM article and not personal experience.)