1Computer

SystemsWuhan

UniversityCourseOverviewComputer

Systems1st

Lecture,

Feb.

21,

2017Instructor:Cien

Fan2OverviewCourse

themeFive

realitiesCourse

ContentCourse

RequirementsLayers

of

Computer

SystemsUtilitiesOperation

SystemComputer

HardwareApplicationEnd

UserProgrammerOperation

SystemDesigner3Why

study

computer

systems?Programming

Lies

at

the

Heart

of

Most

Modern

SystemsComputer

systemsEmbedded

devices: s,

automobile

controls,

…Electronics:

DSPs,

programmable

controllersProgrammersHave

to

Understand

Their

Machines

and

TheirLimitationsCorrectness:

computer

arithmetic,

storage

allocationEfficiency:

memory

&

CPU

performance45Why

study

computer

systems?Knowing

How

to

BuildSystems

Is

Not

the

Way

to

Learn

HowtoProgramThemIt’s

wasteful

to

teach

every

computer

scientist

how

to

design

a

microprocessorKnowledge

of

how

to

build

does

not

transfer

to

knowledge

of

how

to

useWhy

study

computer

systems?Introduce

them

to

computer

systems

from

a

programmer'srather

than

from

a

system

designer’sTopic

Filter: What

parts

of

a

computer

system

affect

thecorrectness,

performance,and

utility

of

my

C

programs?67Where

are

we?From ions

to

details

(realities)From

application

level

to

system

levelFrom

C

toassemblyion

Is

Good

But

Don’t

Forget

RealityMost

CScourses

emphasize

ion?data

typesAsymptoticTheseysisions

have

limitsEspecially

in

the

presence

of

bugsNeed

to

understand

details

of

underlying

implementationsUsefules

from

taking

‘Computer

System’e

more

effective

programmersAble

to

find

and

eliminate

bugs

efficientlyAble

to

understand

and

tune

for

program

performance?Prepare

for

later

“systems”

classesMicroprocessor

System,

Embedded

Systems,

Networks

etc.8Features

of

this

courseEnduring

ConceptsFrom

programmer’sActively

studying

the

rare

“powerprogrammer”9100Enduring

ConceptsComputer

systems

consist

hardware

and

Enduring

conceptssystems

software

that

work

togetherto

run

programsSpecific

implementations

of

systems

change

over

timeButthe

underlying

concepts

donotAll

computer

systems

have

similar

hardware

and

softwarecomponents

that

perform

similar

functions1From

programmer’sWritten

for

programmers

instead

of

system

buildersFew

students

would

have

the

opportunity

to

build

a

computer

systemEven

the

computer

engineers

would

be

required

to

use

and

programcomputers

on

a

daily

basisIt

covers

a

topic

only

if

itaffectedcorrectness,

performance

or

utility

of

user-level

C

programs112From

programmer’sTake

a

broader

and

more

realistic

view

of

the

systemWhat

the

computer

hardware

isHow

modern

computer

works123Actively

studyNew

concepts

are

followed

by

practical

problemsLearning

byproblems

are

also

realngWorking

concrete

problemsWriting

and

running

programs

on

realsystemsPractical,

concrete,

hands-on

and

exciting13144ing

the

rare

“power

programmer”Enlightened

by

an

understanding

ofthe

underlying

computer

systemand

its

impacton

your

application

programsYou

knowHow

things

work

andHow

to

fix

them

when

they

breakGreat

Reality#1:Ints

are

not

Integers,

Floats

are

not

RealsExample

1:

Is

x2

≥

0?Float’s:

Yes!Int’s:40000

*

40000

→

160000000050000

*

50000

→

??Example

2:

Is

(x

+

y)+

z

= x

+

(y

+

z)?Unsigned

&

Signed

Int’s:

Yes!Float’s:(1e20

+

-1e20)

+

3.14-->

3.141e20

+

(-1e20

+

3.14)

-->

??1516Computer

ArithmeticDoes

not

generate

random

valuesArithmetic

operations

have

important

mathematicalpropertiesCannot

assume

all

“usual”

mathematical

propertiesDue

to

finiteness

of

representationsInteger

operations

satisfy

“ring”

propertiesCommutativity,

associativity,distributivityFloating

point

operations

satisfy

“ordering”

propertiesMonotonicity,

values

of

signsObservationNeed

to

understand

which ions

apply

in

which

contextsImportant

issues

for

compiler

writers

and

serious

application

programmersGreat

Reality

#2:You’ve

Got

to

Know

AssemblyChances

are,

you’ll

never

write

programs

in

assemblyCompilers

are

much

better

&

more

patient

than

you

areBut:

Understanding

assembly

is

keytomachine-level

executionmodelBehavior

of

programs

in

presence

of

bugsHigh-level

language

models

break

downTuning

program

performanceUnderstand

optimizations

done

/

not

done

by

the

compilerUnderstanding

sources

of

program

inefficiencyImplementing

system

softwareCompiler

has

machine

code

asOperating

systems

must

manage

process

stateCreating

/

fighting

malwarex86

assembly

is

the

language

of

choice!1718Great

Reality

#3:

Memory

MattersRandom

Access

Memory

Is

an

Unphysical

ionMemory

is

not

unboundedIt

must

be

allocatedand

managedMany

applications

are

memory

dominatedMemory

referencing

bugs

especially

perniciousEffects

are

distant

in

both

time

and

spaceMemory

performance

is

not

uniformCache

and

virtual

memory

effects

can

greatly

affect

program

performanceAdapting

program

to

characteristics

of

memory

system

can

lead

to

majorspeed

improvements19Memory

Referencing

Bug

ExampleResult

is

system

specificfun(0)

→fun(1)

→fun(2)

→fun(3)

→fun(4)

→fun(6)

→3.143.143.13999986648562.000000610351563.14Segmentation

faulttypedef

struct

{int

a[2];double

d;}struct_t;double

fun(int

i)

{volatile

struct_t

s;s.d

=

3.14;s.a[i]

=

1073741824;

/*

Possibly

out

of

bounds

*/return

s.d;}Memory

Referencing

Bug

Exampletypedef

struct

{int

a[2];double

d;}struct_t;Location

accessed

byfun(i)Explanation:Critical

State??d7

...

d4d3

...

d0a[1]a[0]6543210struct_t20fun(0)→3.14fun(1)→3.14fun(2)→3.1399998664856fun(3)

→fun(4)

→fun(6)

→2.000000610351563.14Segmentation

faultMemory

Referencing

ErrorsC

and

C++

do

notprovide

anymemory

protectionOut

of

bounds

arrayreferencesInvalid

pointer

valuesAbuses

of

malloc/freeCan

lead

to

nastybugsWhether

or

not

bug

has

any

effect

depends

on

system

and

compilerAction

at

a

distanceCorrupted

object

logically

unrelated

to

one

being

accessedEffect

of

bug

may

be observed

long

after

it

is

generatedHow

can

I

deal

with

this?Program

in

Java,

Ruby,

Python,

ML,

…Understand

what

possible

interactions

may

occurUse

or

develop

tools

to

detect

referencingerrors

(e.g.

Valgrind)2122Great

Reality

#4:

There’s

more

toperformance

than

asymptotic

complexityConstant

factors

matter

too!And

even

exact

op

count

does

not

predict

performanceEasily

see

10:1

performance

range

depending

on

how

code

writtenMust

optimize

at

multiple

levels:

algorithm,

data

representations,procedures,

and

loopsMust

understand

system

to

optimize

performanceHow

programs

compiled

and

executedHow

to

measure

program

performance

and

identify

bottlenecksHow

to

improve

performance

without

destroying

code

modularity

andgeneralityMemory

System

Performance

Example4.3ms

2.0

GHz

In Core

i7

Haswell

81.8msHierarchical

memory

organizationPerformance

depends

on

access

patternsIncluding

how

step

through

multi-dimensionalarrayvoid

copyji(int

src[2048][2048],int

dst[2048][2048]){int

i,j;for

(j

=

0;

j

<

2048;

j++)for

(i

=

0;

i

<

2048;

i++)dst[i][j]

=

src[i][j];}void

copyij(int

src[2048][2048],int

dst[2048][2048]){int

i,j;for

(i

=

0;

i

<

2048;

i++)for

(j

=

0;

j

<

2048;j++)dst[i][j]

=

src[i][j];}23Why

ThePerformance

Differs128m32m8m2m512k128k32k0200016000140001200010000800060004000s1s3s5s7s9s11Size

(bytes)Read

throughput

(MB/s)Stride

(x8

bytes)copyijcopyji24Great

Reality

#5:Computers

do

more

than

execute

programsThey

need

to

get

data

in

and

outI/O

system

criticalto

program

reliability

and

performanceThey

communicate

with

each

other

over

networksMany

system-level

issues

arise

in

presence

of

networkConcurrent

operations

by

autonomous

processesCo with

unreliable

mediaCross

platform

compatibilityComplex

performance

issues25CourseMost

Systems

Courses

are

Builder-CentricComputer

ArchitectureDesign

pipelined

processor

in

VerilogOperating

SystemsImplement

sample

portions

of

operating

systemCompilersWrite

compiler

for

simple

languageNetworkingImplement

and

simulate

network

protocols26Course

(Cont.)Our

Course

is

Programmer-CentricPurpose

is

to

show

that

by

knowing

more

about

the

underlying

system,one

can

be

more

effective

as

a

programmerEnable

you

toWrite

programs

that

are

more

reliableand

efficientIncorporate

features

that

require

hooks

intoOS

–

E.g.,

concurrency,

signal

handlersCover

material

in

this

course

that

you

won’t

see

elsewhereNot

just

a

course

for

dedicated

hackersWe

bring

out

the

hidden

hacker

in

everyone!27Role

within

CS

CurriculumOperatingSystemsCompilersProcessesMem.

MgmtNetworksNetworkProtocolsArchitectureEmbeddedSystemsDatabasesData

Reps.MemoryModelDigitalComputationMachineCodeArithmeticEmbeddedSystem

Eng.Foundation

of

Computer

SystemsUnderlying

principles

for

hardware,software,

and

networkingExecution

ModelMemory

SystemComputerSystemDistributedsystemsNetwork

ProgConcurrency28Textbooks《深入理解計算機系統》（原書第3版），機械工業，[美]蘭德爾E.布萊恩特（RandalE.Bryant）等著，龔奕利，賀蓮譯，2016《Computer

Systems——AProgrammer’s

》(3rdEdition),Randal

E.

Bryant,David

R.O’Hallaron,2016.2930Wuhan

UniversityCourse

content周次1學時3內容—計算機系統漫游二計算機信息的表示和處理信息整數表示二計算機信息的表示和處理整數運算浮點數三程序的機器級表示歷史觀點程序編碼數據格式4.信息233343Course

content周次內容三、程序的機器級表示數組分配和異質的數據結構理解指針和緩沖區3.12

器的越界四、處理器體系結構4.1

Y86指令集體系結構四、處理器體系結構Y86的順序實現

四、處理器體系結構流水線的通用原理Y86的流水線實現學時5363738331Course

content周次內容學時9五、優化程序性能5