صفحه 1:
15-213
“The Class That Gives CMUlIts Zip!’
Introduction to
Computer Systems
و
January 16,2007
Topics:
* Theme
* Fiwegreat realities of computer systems
* اقلا لنت ا جئدت كا نااك ابد وناو ك6 ج34
classOla.ppt موی
صفحه 2:
Course Theme
Abstraction is good, but don’t forget reality!
Courses to dateemphasizeabstraction
° Abstract datatypes
* Asymptoticanalysis
These abstractions have limits
۰ Especiallyin thepresence of bugs
* Needtounderstandunderlying implementations
Useful outcomes
* Becomemoreeffectiveprogrammers
- Able tofindandeliminate bugsefficiently
- Able totuneprogramperformance
* Preparefor Cater “systems” classes
- Compilers, Operating Systems, Networks, Computer Architecture
دی 2 مم ها
صفحه 3:
Great Reality #7
Int’sarenot Integers, Float’sarenot Reals
Examples
* مروز 67
- Float's: Ves!
- Int’s:
» 65535 * 65535 --> -131071 (On most machines)
» 65535L * 65535 --> 4292836225 (OnACpha)
۶ Is(xt+y)+z = x4(y+z)?
-‘UnsignedInt's: Yes!
- Float's:
« )1610 + -1610( + 3.14 --< 4
» 1e10 + (-1e10 + 3.14) --> 0.0
دی ۳ مم ها
صفحه 4:
Computer Arithmetic
Does not generaterandomvalues
* Arithmetic operations haveimportant mathematical properties
Cannot assume “usual” properties
* Duetofiniteness of representations
* Integer operations satisfy “ring” properties (usually)
- Commutativity, associativity, distributivity
* Floating point operations satisfy ‘ordering’ properties
- Monotonicity,vaCues of signs
Observation
° Neektounderstandwhichabstractionsapplyin whichcontexts
* Important issuesfor compiler writersandserious application
programmers
دی ‘ مم ها
صفحه 5:
Great Reality #2
You’ve got toknow assembly
Chances are,yow(l never write programin assembly
* Compilers aremuch better at thisthan- youare
‘Understanding assembly key tomachine-Cevel execution
model
* Behavior ofprogramsin presence of bugs
~ High-Level Canguage model breaks down
* Tuning programperformance
- Understanding sources of programinefficiency
* Implementing system software
~ Compiler hasmachinecodeas target
- Operating systems must manage process state
classOla.ppt 5 دی
صفحه 6:
Great Reality #3
Memory Matters
Memory isnot unbounded
* Itmust beallocatedandmanaged
* Manyapplicationsarememory dominated
* ‘Thememory systemcan be the largest portion of amachine’scost
Memory referencing bugs especially pernicious
* Sffectsare distant inbothtimeandspace
Memory performanceis not uniform
* Cacheandvirtual memory effects can greatly affect program
performance
* Adaptingprogramtocharacteristics of memory systemcanleadto
mafor speedimprovements
مم ها
دی
صفحه 7:
Memory Referencing Bug Example
main ()
1
long int a[2];
double d = 3.14;
a[2] = 1073741824; /* Out of bounds reference */
printf("d = %.15g\n", d);
exit (0);
Alpha MIPS Sum
-g 5.30498947741318e-315 3.1399998664856 3.14
-0 3.14 3.14 3.14
دی 5 مم ها
صفحه 8:
Memory Referencing Errors
CandC++ donot provideanymemory protection
* Out of6oundsarrayreferences
* Invalidpointer-vatues
* abuses ofmatloc/free
Canleadto nasty bugs
* ‘Whether or not bug has any effect systemandcompiler dependent
* Actionata distance
- Corrupted object Cogicallyunrelatedtoonebeing accessed
~ Effect of bug may occur Cong after it occurs
How canI deal-withthis?
* Programin Java, Lisp,or ML
* Understandwhat possibleinteractionsmay occur
* Alseor develop tools to detect referencingerrors
- E.g.,Purify
دی ۰ مم ها
صفحه 9:
sum += afi][k] * b{k][j];
Memory Performance Example
Implementations of Matrix Multiplication
* Multiplewaystonest Coops
7* 7
for (j=0; jen; j++) {
for ( icn; i++) {
sum = 0.0;
for (k=0; k<nj k++)
7۳۰106
icn; itt) 4
isn; j++) {
sum += a[i][k] * b{k][j];
e(i][j] = sum;
clil{j] = sum
}
1
class0la.ppt ۲ دی
صفحه 10:
Matmult Performance (Alpha 21164)
ToobigfortrCache Toobigfor£2Cache
0 =
ا مه
انز و
از هه
i] سر
إن و
PEP SPE LE PELE PEEL EEE LS
matrix size (n)
دی ۳ مم ها
flops (4.p.)
صفحه 11:
Blockedmatmult perf (Alpha 27764)
اه هم
ik ی
> ی
هه هها
160
50 75 100 125 150 175 200 225 250 275 300 325 350 375 400 425 450 475 0
matrix size (n)
7 353200
class0la.ppt
mflops (4.p.)
صفحه 12:
Great Reality #4
There'smore to performance than asymptotic complexity
Constant factorsmatter too!
* Easily see 10:7 performance range depending on القع !1 جرح عه ام
° Must optimizeat multiple levels:algorithm, data representations,
procedures,andloops
Must understandsystem to optimize performance
* sfowprograms compiledandexecuted
* Sow tomeasureprogramperformanceandidentify bottlenecks
* Stow toimproveperformance without destroying codemodularity and
generality
دی 2 مم ها
صفحه 13:
Great Reality #5
Computers domore than execute programs
They needtoget datainandout
* T/Osystemcritical toprogramreliabilityandperformance
They communicate witheachother over networks
* Many system-Level issues arisein presence of network
- Concurrent operations by autonomous processes
- Coping withunreliablemedia
~ Cross platformcompatibility
~ Complex performance issues
دی ۳ مم ها
صفحه 14:
اانا سدع )م1
Curriculum
Network ‘Processes MachineCode
Protocols Mem. Mgmt Optimization
‘Exec. Model
S212 ‘MemorySystem
sein | | oa, سا
Models ۷
1
Data Structures TransitionfromAbstract to
Applications
Programming Concrete!
* From:high-Cevel Canguagemodel
save * Torunderlying implementation
Fundamental
Structures
دی مم ها