Group members

Patrick Young Rannath@gmail.com

Daniel Beimers demongyro@gmail.com

Andrew Bown abown2@connect.carleton.ca

Kirill Kashigin k.kashigin@gmail.com

Rovic Perdon rperdon@gmail.com

Methodology

We should probably have our work verified by at least one group member before posting to the actual page

To Do

Improve the grammar/structure of the paper section
Background Concepts -fill in info (fii)
Research problem -fii
Contribution -fii
Critique -fii
References -fii

Claim Sections

I claim Exim and memcached for background and critique -Rannath
also per-core data structures, false sharing and unessesary locking for contribution -Rannath

Essay

Paper

This paper was authored by - Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich.

They all work at MIT CSAIL.

The paper: An Analysis of Linux Scalability to Many Cores

Background Concepts

Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.

Ideas to explain:
- thread (maybe)
- Linux's move towards scalability precedes this paper. (assert this, no explanation needed, maybe a few examples)
- Summarize scalability tutorial (Section 4.1 of the paper)
- Describe the programs tested (what they do, how they're programmed (serial vs parallel), where to the do their processing)

Exim: Section 3.1

Exim is a mail server for Unix. It's fairly parallel. The server forks a new process for each connection and twice to deliver each message. It spends 69% of its time in the kernel on a single core.

memchached: Section 3.2

memcached is an in-memory hash table. memchached is very much not parallel, but can be made to be, just run multiple instances. Have clients worry about synchronizing data between the different instances. With few requests memcached does most of its processing at the network stack, 80% of its time on one core.

Apache: Section 3.3

PostgreSQL: Section 3.4

gmake: Section 3.5

Psearchy: Section 3.6

Metis: Section 3.7

Research problem

What is the research problem being addressed by the paper? How does this problem relate to past related work?

Problem being addressed: scalability of current generation OS architecture, using Linux as an example. (?)

Summarize related works (Section 2, include links, expand information to have at least a summary of some related work)

Contribution

What was implemented? Why is it any better than what came before?

Summarize info from Section 4.2 onwards, maybe put graphs from Section 5 here to provide support for improvements (if that isn't unethical/illegal)?

Conclusion: we can make a traditional OS architecture scale (at least to 48 cores), we just have to remove bottlenecks.

Multicore packet processing: Section 4.2

Sloppy counters: Section 4.3

Lock-free comparison: Section 4.4

Per-Core Data Structures: Section 4.5

Three centralized data structures were causing bottlenecks - a per-superblock list of open files, vfsmount table, the packet buffers free list. Each data structure was decentralized to per-core versions of itself. In the case of vfsmount the central data structure was maintained, and any per-core misses got written from the central table to the per-core table.

Eliminating false sharing: Section 4.6

Misplaced variables on the cache cause different cores to request the same line to be read and written at the same time often enough to significantly impact performance. By moving the often written variable to another line the bottleneck was removed.

Avoiding unnecessary locking: Section 4.7

Many locks/mutexes have special cases where they don't need to lock. Likewise mutexes can be split from locking the whole data structure to locking a part of it. Both these changes remove or reduce bottlenecks.

Critique

What is good and not-so-good about this paper? You may discuss both the style and content; be sure to ground your discussion with specific references. Simple assertions that something is good or bad is not enough - you must explain why.

Since this is a "my implementation is better then your implementation" paper the "goodness" of content can be impartially determined by its fairness and the honesty of the authors.

Content(Fairness): Section 5

Fairness criterion:
- does the test accurately describe real-world use-cases (or some set there-of)? (external fairness, maybe ignored for testing and benchmarking purposes, usually is too)
- does the test put all tested implementations through the same test? (internal fairness)

Both the stock and new implementations use the same benchmarks, therefore internal fairness is preserved for all seven programs.

Exim: Section 5.2

The test uses a relatively small number of connections, but that is also implicitly stated to be a non-issue - "as long as there are enough clients to keep Exim busy, the number of clients has little effect on performance."

This test is explicitly stated to be ignoring the real-world constraint of the IO bottleneck, thus is unfair when compared to real-world scenarios. The purpose was not to test the IO bottleneck. Therefore the unfairness to real-world scenarios is unimportant.

memcached: Section 5.3

memcached has no explicit or implicit fairness concerns with respect to real-world scenarios.

Apache: Section 5.4

PostgreSQL: Section 5.5

gmake: Section 5.6

Psearchy: Section 5.7

Metis: Section 5.8

Style

Style Criterion (feel free to add I have no idea what should go here):
- does the paper present information out of order?
- does the paper present needless information?
- does the paper have any sections that are inherently confusing?

References

You will almost certainly have to refer to other resources; please cite these resources in the style of citation of the papers assigned (inlined numbered references). Place your bibliographic entries in this section.