IntroductionThe Parallel LandscapeVectors will be VictorsQuantifying Redundant ExecutionScaling Redundancy With LoadTowards the Vector OSInterface OptionsDiscussionConclusionThe Case for VOS: The Vector Operating SystemVijay Vasudevan, David G. Andersen, Michael Kaminsky1Carnegie Mellon University,1Intel LabsAbstractOperating systems research for many-core systems hasrecently focused its efforts on supporting the scalability ofOS-intensive applications running on increasingly paral-lel hardware. Lost amidst the march towards this parallelfuture is efficiency: Perfectly parallel software may sat-urate the parallel capabilities of the host system, but indoing so can waste hardware resources.This paper describes our motivation for the Vector OS,a design inspired by vector processing systems that pro-vides efficient parallelism. The Vector OS organizes andexecutes requests for operating system resources through“vector” interfaces that operate on vectors of objects. Weargue that these interfaces allow the OS to capitalize on nu-merous chances to both eliminate redundant work foundin OS-intensive systems and use the underlying paral-lel hardware to its full capability, opportunities that aremissed by existing operating systems.1 IntroductionOver the last decade, computing hardware has promisedand delivered performance improvements by providingincreasingly parallel hardware. Systems with multi-coreCPUs, and GPUs with hundreds of cores have becomethe norm. The gauntlet has been firmly thrown down atthe software community, who have been tasked to takeadvantage of this increased hardware parallelism.The operating systems community has largely risento the challenge, presenting new OS architectures andmodifying existing operating systems that enable paral-lelism for the many-core era [2,12,3,4]. Independently,application writers have rewritten or modified their appli-cations to use novel parallel programming libraries andtechniques. Both communities have improved softwarewithout changing how applications request OS resources.In this paper, we argue that OS-intensive parallel ap-plications, including many of today’s driving datacenterapplications, must be able to express requests to the oper-ating system using a vector interface in order to give theOS the information it needs to execute these demands ef-ficiently. To not do so will make “embarrassingly parallel”workloads embarrassingly wasteful. We outline a new de-sign, the Vector OS (VOS), that is able to let OS-intensiveapplications be not just parallel, but efficiently parallel.Consider a modern webserver that receives a newconnection using theaccept()system call.accept()returns exactly one connection from a list of pendingconnections. The application then performs a series ofsequential operations to handle the connection—setup,application-specific processing, and teardown. A high-load webserver may be serving many requests in parallel,but each request follows similar execution paths, wastingresources executing redundant work that could be sharedacross concurrent requests.In VOS, work is executed using vector operations thatare specified through vector interfaces likevec accept()(which returns multiple connections rather than just one),vec open(),vec read(),vec send(), etc. Exposingvector interfaces between applications and the operat-ing system improves efficiency by eliminating redundantwork; moreover, vector interfaces open the door to newefficiency opportunities by allowing VOS to more effec-tively harness vector and parallel hardware capabilitiesalready present in many machines, such as SSE vectorinstructions and GPUs.This paper argues that vector interfaces are critical toachieving efficient parallelism, thus requiring changesto the OS interface that applications program to. Butthis departure from a decades-old interface raises severalquestions and challenges that are as exciting as they aredifficult: Should developers explicitly specify work interms of vectors of resources? If not, how should vectorexecution be hidden from the programmer without intro-ducing excessive complexity into the OS? What are thesemantics of vector system call completion? Should theybe synchronous or asynchronous, and how should theyhandle exceptions? We address many of these questionsin this paper, but do not yet have answers to all of them.Nonetheless, we believe that the Vector OS can enableOS-intensive applications to make the maximum use oftoday’s increasingly vector and parallel hardware.2 The Parallel LandscapeHardware parallelism is growing.Processors continueto gain speed by adding cores; graphics engines improverendering performance by adding shaders; solid state1open(f): 1. context switch 2. alloc() 3. copy(f) 4. path_resolve(f): acl_check(f) h = hash(f) lookup(h) 5. read(f) 6. dealloc() 7. context switch vec_open([f1,f2,f3]): 1. context switch 2. vec_alloc() 3. vec_copy([f1,f2,f3]) 4. vec_path_resolve([f1,f2,f3]): vec_acl_check([f1,f2,f3]) hset = vec_hash([f1,f2,f3]) vec_lookup(hset) 6. vec_dealloc() 7. context switchRedundancy eliminated}Redundancy eliminated if joined}}Parallelizable}SSE}Redundancy eliminated}Redundancy eliminated5a. vec_read_xfs([f1]) 5b. vec_read_ext4([f2,f3])Figure 1: Pseudocode for open() and proposed vec open(). vec open() provides opportunities for eliminatingredundant code execution, vector execution when possible, and parallel execution otherwise.drives improve throughput by adding more flash chips;and CPUs increase throughput by making their vectorinstructions, such as SSE, even wider.1These trends areexpected to continue into the foreseeable future, barring arevolution in device physics.OS-intensive, parallel applications are adapting toparallel hardware. memcachedmoved from single-threaded to multi-threaded; event-based webservers suchasnode.jsand Python Twisted are improving support formassive concurrency; languages and threading librariessuch as OpenMP, Cilk, Intel Thread Building Blocks, andApple’s Grand Central Dispatch library all encourage ap-plications to break work into smaller independent tasks,which the libraries can then assign to cores.Parallel operating systems are making parallel ex-ecution possible.Recent work on improving operatingsystem support for parallelism