A N t C t A Note on Computer Systems Researchcsl.skku.edu/uploads/ECE5658M10/1-research.pdf · Comppy ()uter Systems Research (3) Desiggg p y yning computer systems is very different

A N t C t A N t C t A Note on Computer Systems Research

A Note on Computer Systems ResearchSystems ResearchSystems Research

Jin-Soo Kim ([email protected])Jin Soo Kim ([email protected])Computer Systems Laboratory

Sungkyunkwan Universityhtt // l kk dhttp://csl.skku.edu

Computer Systems (1)Computer Systems (1)Computer Systems (1)Computer Systems (1) Computer systemsp y

2ECE5658: Operating System Design | Summer 2010 | Jin-Soo Kim ([email protected])

Computer Systems (2)Computer Systems (2)Computer Systems (2)Computer Systems (2)

Software Application

Operating Systems

Architecture

I/O Devices

Architecture

CPU Mem/

Hardware


Computer Systems Research (1)Computer Systems Research (1)p y ( )p y ( )

What is computer systems research?p y• Dealing with everything between hardware and

applications.• The capstone of all the computer science principles:

– Operating systems– Computer architecture– Computer networks

Compilers– Compilers– Programming languages– Databases– Security– Data structures


– Algorithms, …


Computer systems area includesp y• Parallel systems, Cluster systems• Distributed systems, Grid computingy , p g• Embedded systems• Storage systemsSto age syste s• Network appliances• P2P systemsP2P systems• Database management systems• Mobile computingMobile computing• Ubiquitous (pervasive) computing• and you name it!


• … and you name it!


Designing computer systems is very different g g p y yfrom designing an algorithm:• The external requirement is less precisely defined, q p y ,

more complex, and more subject to change.

• The system has much more internal structure, hence many internal interfaces.

• The measure of success is much less clear.



Challenges• Large system is difficult to understand.• There are not necessarily any right answers.

– There is a sea of possibilities.– Unclear about how one choice will limit his freedom to make

other choices, or affect the size and performance of the pentire system.

• No one can tell you with certainty that you are right.The best way we can do is to avoid choosing a terrible way– The best way we can do is to avoid choosing a terrible way.

– The art of trade-offs.

• You are never done.– The last 10% to perfection typically consumes 80% of the

effort.You don’t know if the resulting system is perfect or not


– You don t know if the resulting system is perfect or not.

Systems Research CyclesSystems Research CyclesSystems Research CyclesSystems Research Cycles

dM ti ti IdeaMotivation

Design

Prototyping

benchmarksOptimization

Measurementbenchmarksmethodology

Analysis

Papers Patents $$$


Papers, Patents, $$$

Motivation & Idea (1)Motivation & Idea (1)Motivation & Idea (1)Motivation & Idea (1) Identify a problem/phenomenon in the current

systems:• Physical memories are small.

CPU i tti f t b t I/O i NOT th t h• CPU is getting faster but I/O is NOT that much. …

The world is changing:• New services: WWW Web services LBS P2P Grid MMORPG• New services: WWW, Web services, LBS, P2P, Grid, MMORPG, …• New applications: DB, Java, Games, …• New environments: Wireless, Mobile, Ad-hoc, Embedded, , , , ,

Battery-powered, …• New architecture/devices: Sensors, Flash memories, …

Add f i li Add a functionality, Enhance performance/reliability, orDevelop a new system


Develop a new system

Motivation & Idea (2)Motivation & Idea (2)Motivation & Idea (2)Motivation & Idea (2) Some suggestionsgg

• Have a broad spectrum of knowledge.– Read widely.– Don’t stick to your *field*. (Bad Career Move #1)

• Know the state-of-the-art technology.– See what other people are doing.

• Stay tuned for emerging technologies and predict th i i li titheir implications.

• Be a team player; discuss with others.Th i f l h• There is no free lunch. – Practice solving problems and building systems whenever

you have a chance.


you have a chance.

Design (1)Design (1)Design (1)Design (1) Three basic questionsq

• Functionality: – Does it work?

• Speed: – Is it fast enough?

• Fault-tolerance: – Does it keep working?

(cf ) B Lampson “Hints for Computer System Design ” SOSP 1983(cf.) B. Lampson, Hints for Computer System Design, SOSP, 1983.


Design (2)Design (2)Design (2)Design (2) Functionality: Does it work?y

• Keep it simple:– Do one thing at a time, and do it well.– Get it right.– Make it fast, rather than general or powerful.

D ’t hid– Don’t hide power.– Use procedure arguments to provide flexibility in an

interface.– Leave it to the client.


Design (3)Design (3)Design (3)Design (3) Functionality: Does it work? (cont’d)y ( )

• Continuity:– Keep basic interfaces stable.– Keep a place to stand if you do have to change interfaces.

• Making implementations work:– Plan to throw one away.– Keep secrets of the implementation.

Divide and conquer– Divide and conquer.– Use a good idea again instead of generalizing it.

• Handling all the cases:Handling all the cases:– Handle normal and worst cases separately.


Design (4)Design (4)Design (4)Design (4) Speed: Is it fast enough?

• Split resources in a fixed way if in doubt, rather than sharing them.

• Use static analysis if you can• Use static analysis if you can.• Use a dynamic translation from a convenient representation to

one that can be quickly interpreted.• Cache answers to expensive computations, rather than doing

them over.• Use hints to speed up normal execution• Use hints to speed up normal execution.• When in doubt, use brute force.• Compute in background when possible.p g p• Use batch processing if possible.• Safety first.

h d l d l d d h h ll h


• Shed load to control demand, rather than allowing the system to become overloaded.

Design (5)Design (5)Design (5)Design (5) Fault tolerance: Does it keep working?p g

• End-to-end error recovery• Log updates to record the truth about the state of an g p

object.• Make actions atomic or restartable.


Design (6)Design (6)Design (6)Design (6) Summaryy


Design (7)Design (7)Design (7)Design (7) Some suggestionsgg

• Ask why you are doing this.– Define your motivation, goals, and metrics first.

• And then, ask Who? When? What? How?

• List the expected benefits and costs• List the expected benefits and costs.– BEFORE any experiments.– Determine the graphs you would like to see.g p y

• Think of any other way you can do better.– Implementations are expensive; take enough time on design.

• Again, be a team player; review your design with others.


others.– Two heads are better than one.

Policy vs. Mechanism (1)Policy vs. Mechanism (1)Policy vs. Mechanism (1)Policy vs. Mechanism (1) Policyy

• What should be done?• Policy decisions must be made for all resource y

allocation and scheduling problems.– CPU scheduling: scheduling algorithm, quantum size, etc.

Mechanism• How to do something?• The tool for implementing a set of policies.

– CPU scheduling: dispatcher for low-level context switching, priority queues, etc.X windows implement “mechanism not policy”


– X-windows implement mechanism, not policy .

Policy vs. Mechanism (2)Policy vs. Mechanism (2)Policy vs. Mechanism (2)Policy vs. Mechanism (2) Separating policy and mechanismp g p y

• A key principle in operating system design.• Policies are likely to change depending on workloads, y g p g ,

and also across places or over time.– Each change in policy would require a change in the

d l i h iunderlying mechanism.

• A general mechanism, separated from policy, is more desirabledesirable.– A change in policy would then require redefinition of only

certain parameters of the system instead of resulting in a change in the mechanism.

– It is possible to experiment with new policy without breaking mechanisms


mechanisms.

Policy vs. Mechanism (3)Policy vs. Mechanism (3)Policy vs. Mechanism (3)Policy vs. Mechanism (3) Separating policy and mechanism (cont’d)p g p y ( )

• Allows to build a more modular OS.– Only need to port mechanisms.

• Enables extensible systems.– Microkernel only implements a basic set of policy free

i itiprimitives.– More advanced mechanisms and policies are added via user-

created kernel-modules or via user programs themselves.p g

• One can design a kernel that allows processes to download their ideal policies directly into the OS.


Evaluation (1)Evaluation (1)Evaluation (1)Evaluation (1) Evaluation methodologies

• Use analytical investigations– Probably too many assumptions.

N d t i j t l t H t bt i th ?– Need to inject real parameters… How to obtain them?

• Use simulations– OK if you use a well-known simulator.OK if you use a well known simulator.– Need to prove your model is correct; run sanity checking

experiments to which you know the answer.

G th t f l t• Gather traces from real systems– Traces are much easier to deal with.

• Instrument or modify existing systemsInstrument or modify existing systems– Hard…

• Build prototypes.


– Harder…

Evaluation (2)Evaluation (2)Evaluation (2)Evaluation (2) Use scientific method

• Hypothesis• Measure

S f i• Measure• Measure, again

Sequence of experimentsChange 1 parameter/experiment

easu e, aga• Compare results against other’s results• Prove/Disprove hypothesisProve/Disprove hypothesis• Modify or suggest new hypothesis• Document for others to reproduce resultsDocument for others to reproduce results

• Use your intuition to ask questions, not answer them.


• What’s your metric?

Writing a Research Paper (1)Writing a Research Paper (1)Writing a Research Paper (1)Writing a Research Paper (1) Abstract

• Introduce area • State problem• Summarize conclusions (be quantitative)Summarize conclusions (be quantitative)

Introduction• Complete description of problem• State more detailed results• Short summary of what’s have been done• Roadmap of the paper• Roadmap of the paper

Previous work• Do a thorough literature search (from 60’s)• Neither more nor less list of references• Relate your work to existing work• Demonstrate how your work fits in to the grand scheme of


• Demonstrate how your work fits in to the grand scheme of things

Writing a Research Paper (2)Writing a Research Paper (2)Writing a Research Paper (2)Writing a Research Paper (2) What you did

• Do describe your research• Be thorough, but concise

The results• Describe experimental setup• Explain expected results, reasons for such expectation• Explain surprising difference• Visual presentation of data• Visual presentation of data

Conclusions• State results again• State significance of results• Tell people what they should have learned


• Tell people what they should have learned

Writing a Research Paper (3)Writing a Research Paper (3)Writing a Research Paper (3)Writing a Research Paper (3) Future work

• What questions still remain• What new questions have arisen• How can your work be extendedHow can your work be extended

General tips• Spell-check: very important• Grammar-check: very difficult for us• Style check: passive voice plural he/she• Style check: passive voice, plural, he/she, …• Let the paper sit for a few days before proof reading• As research is going on, starts writing• Write early• Write often: very important • Read many papers!


Read many papers!

Conclusion (1)Conclusion (1)Conclusion (1)Conclusion (1) Evaluation criteria for systems research:y

• Originality of ideas• Availability of real implementationsy p• Importance of lessons learned• Exploration of alternative design choicesp o at o o a te at e des g c o ces• Soundness of assumptions

How to extend?How to extend?• New functionality?• Performance?• Performance?• Reliability?• Energy efficiency?


• Energy efficiency?

Conclusion (2)Conclusion (2)Conclusion (2)Conclusion (2) Systems research is multifaceted:y

• Science– Discover truth by scientific methods.

• Engineering– Achieve a solution that works for a particular problem.– Develop “good enough” heuristics.

• ArtEl b d i li i– Elegance, beauty, and simplicity.

– Make complex ideas more palatable or more comprehensible.p


ReferencesReferencesReferencesReferences

• B. W. Lampson, “Hints for Computer System Design,” OperatingB. W. Lampson, Hints for Computer System Design, Operating Systems Review, 15:5, Oct. 1983, pp33-48.

• J. H. Saltzer, D. P. Reed, and D. D. Clark, “End-to-end Arguments gin System Design,” Proc. of the 2nd Int’l Conf. on Distributed Computing Systems, Apr. 1981, pp.509-512.

R L i d D D R d ll “A E l i f h Ni h SOSP• R. Levin and D. D. Redell, “An Evaluation of the Ninth SOSP Submissions or How (and How Not) to Write a Good Systems Paper,” Operating Systems Review, 17:3, July 1983, pp.35-40.

• D. Patterson, “How to Have a Bad Career in Research/Academia,” CRA Academic Careers Workshop, 2002.

• A. Brown, A. Chanda, R. Farrow, A. Fedorova, P. Maniatis, and M. Scott, “The Many Faces of Systems Research – And How to Evaluate Them ” HotOS 2005


Evaluate Them, HotOS, 2005.

Documents

A N t C t A Note on Computer Systems Researchcsl.skku.edu/uploads/ECE5658M10/1-research.pdf · Comppy ()uter Systems Research (3) Desiggg p y yning computer systems is very different