University

 of  Washington  

The  Hardware/So7ware  Interface  

CSE351  Summer  2013  

Instructor:    
Benjamin  Wood  
 
Teaching  Assistants:  
Jacob  Gile,  Riley  Klingler  

1  
 University  of  Washington  

Course  Staff  

Ben  
instructor  

Jacob   Riley  
TA   TA  

Winter  2013   IntroducCon   2  

 University  of  Washington  

Who  are  you?  

¢  22ish  students  

¢  Majors,  non-­‐majors  

¢  Fans  of  computer  science,  no  doubt!  

¢  Who  has  wriRen  a  program:  

§  in  Java?  
§  in  C?  
§  in  Assembly  language?  
§  with  mulGple  threads?  

3  
 University  of  Washington  

Quick  Announcements  
¢  Website:  cs.uw.edu/351  
¢  SecCon  locaCon  to  be  updated  soon…  
¢  Lab  0  released,  due  Friday  5pm.  
§  Simple  exercises  to  get  familiar  with  C.  
§  Credit/no-­‐credit.  

4  
 University  of  Washington  

The  Hardware/So7ware  Interface  

¢  What  is  hardware?  So7ware?  

¢  What  is  an  interface?  

¢  Why  do  we  need  a  hardware/so7ware  interface?  

¢  Why  do  we  need  to  understand  both  sides  of  this  interface?  

5  
 University  of  Washington  

C/Java,  assembly,  and  machine  code  

if (x != 0) y = (y+z)/x;!

cmpl $0, -4(%ebp) 1000001101111100001001000001110000000000

je .L2 0111010000011000
movl -12(%ebp), %eax 10001011010001000010010000010100
movl -8(%ebp), %edx 10001011010001100010010100010100
leal (%edx, %eax), %eax 100011010000010000000010
movl %eax, %edx 1000100111000010
sarl $31, %edx 110000011111101000011111
idivl -4(%ebp) 11110111011111000010010000011100
movl %eax, -8(%ebp) 10001001010001000010010000011000
.L2:

6  
 University  of  Washington  

C/Java,  assembly,  and  machine  code  

if (x != 0) y = (y+z)/x;!

ê  
cmpl $0, -4(%ebp) 1000001101111100001001000001110000000000
je .L2 0111010000011000
movl -12(%ebp), %eax 10001011010001000010010000010100
movl -8(%ebp), %edx è 10001011010001100010010100010100
leal (%edx, %eax), %eax 100011010000010000000010
movl %eax, %edx 1000100111000010
sarl
idivl
$31, %edx
-4(%ebp)
ç   110000011111101000011111
11110111011111000010010000011100
movl %eax, -8(%ebp) 10001001010001000010010000011000
.L2:

l  The  three  program  fragments  are  equivalent  

l  You'd  rather  write  C!    -­‐  a  more  human-­‐friendly  language  
l  The  hardware  likes  bit  strings!    -­‐  everything  is  voltages  
l  The  machine  instrucGons  are  actually  much  shorter  than  the  number  of  
bits  we  would  need  to  represent  the  characters  in  the  assembly  language  
7  
 University  of  Washington  

HW/SW  Interface:  The  Historical  PerspecCve  

¢  Hardware  started  out  quite  primiCve  
§  Hardware  designs  were  expensive  ⇒  instrucGons  had  to  be  very  simple  
–  e.g.,  a  single  instrucGon  for  adding  two  integers  
¢  So7ware  was  also  very  basic  
§  SoQware  primiGves  reflected  the  hardware  preSy  closely  

Architecture Specification (Interface)

Hardware

8  
 University  of  Washington  

HW/SW  Interface:  Assemblers  

¢  Life  was  made  a  lot  beRer  by  assemblers  
§  1  assembly  instrucGon  =  1  machine  instrucGon,  but...  
§  different  syntax:  assembly  instrucGons  are  character  strings,  not  bit  
strings,  a  lot  easier  to  read/write  by  humans  
§  can  use  symbolic  names  
Assembler specification

User
program
in Assembler Hardware
asm

9  
 University  of  Washington  

HW/SW  Interface:  Higher-­‐Level  Languages  

¢  Higher  level  of  abstracCon:  
§  1  line  of  a  high-­‐level  language  is  compiled  into  many  (someGmes  very  
many)  lines  of  assembly  language  

C language specification

User
program C Assembler Hardware
in C compiler

10  
 University  of  Washington  

HW/SW  Interface:  Code  /  Compile  /  Run  Times  

Code  Time   Compile  Time   Run  Time  

User
program C Assembler Hardware
in C compiler

.c file .exe file

Note: The compiler and assembler are just programs, developed using
this same process.

11  
 University  of  Washington  

Outline  for  today  

¢  Course  themes:  big  and  liRle  
¢  Roadmap  of  course  topics  
¢  Three  important  realiCes  
¢  How  the  course  fits  into  the  CSE  curriculum  
¢  LogisCcs  

12  
 University  of  Washington  

The  Big  Theme:  Interfaces  and  AbstracCons  

¢  CompuCng  is  about  abstracCons  
§  (but  we  can’t  forget  reality)  
¢  What  are  the  abstracCons  that  we  use?  
¢  What  do  YOU  need  to  know  about  them?  
§  When  do  they  break  down  and  you  have  to  peek  under  the  hood?  
§  What  bugs  can  they  cause  and  how  do  you  find  them?  
¢  How  does  the  hardware  (0s  and  1s,  processor  execuCng  
instrucCons)  relate  to  the  so7ware  (C/Java  programs)?  
§  Become  a  beSer  programmer  and  begin  to  understand  the  important  
concepts  that  have  evolved  in  building  ever  more  complex  computer  
systems  

13  
 University  of  Washington  

Roadmap   Memory,  data,  &  

addressing  
Integers  &  floats  
C:   Java:  
Machine  code  &  C  
car *c = malloc(sizeof(car)); Car c = new Car(); x86  assembly  
c->miles = 100; c.setMiles(100); Procedures  &  stacks  
c->gals = 17; c.setGals(17);
float mpg = get_mpg(c); float mpg =
Arrays  &  structs  
free(c); c.getMPG(); Memory  &  caches  
Processes  
Assembly   get_mpg: Virtual  memory  
language:   pushq %rbp Memory  allocaCon  
movq %rsp, %rbp Java  vs.  C  
...
popq %rbp
ret
OS:  
Machine   0111010000011000
100011010000010000000010
code:   1000100111000010
110000011111101000011111

Computer  
system:  

Roadmap  
 University  of  Washington  

LiRle  Theme  1:  RepresentaCon  

¢  All  digital  systems  represent  everything  as  0s  and  1s  
§  The  0  and  1  are  really  two  different  voltage  ranges  in  the  wires  
¢  “Everything”  includes:  
§  Numbers  –  integers  and  floaGng  point  
§  Characters  –  the  building  blocks  of  strings  
§  InstrucGons  –  the  direcGves  to  the  CPU  that  make  up  a  program  
§  Pointers  –  addresses  of  data  objects  stored  away  in  memory  
¢  These  encodings  are  stored  throughout  a  computer  system  
§  In  registers,  caches,  memories,  disks,  etc.  
¢  They  all  need  addresses  
§  A  way  to  find  them  
§  Find  a  new  place  to  put  a  new  item    
§  Reclaim  the  place  in  memory  when  data  no  longer  needed  
15  
 University  of  Washington  

LiRle  Theme  2:  TranslaCon  

¢  There  is  a  big  gap  between  how  we  think  about  programs  and  
data  and  the  0s  and  1s  of  computers  
¢  Need  languages  to  describe  what  we  mean  
¢  Languages  need  to  be  translated  one  step  at  a  Cme  
§  Words,  phrases  and  grammars  
¢  We  know  Java  as  a  programming  language  
§  Have  to  work  our  way  down  to  the  0s  and  1s  of  computers  
§  Try  not  to  lose  anything  in  translaGon!  
§  We’ll  encounter  Java  byte-­‐codes,  C  language,  assembly  language,  and  
machine  code  (for  the  X86  family  of  CPU  architectures)  

16  
 University  of  Washington  

LiRle  Theme  3:  Control  Flow  

¢  How  do  computers  orchestrate  the  many  things  they  are  
doing?  
¢  In  one  program:  
§  How  do  we  implement  if/else,  loops,  switches?  
§  What  do  we  have  to  keep  track  of  when  we  call  a  procedure,  and  then  
another,  and  then  another,  and  so  on?  
§  How  do  we  know  what  to  do  upon  “return”?  
¢  Across  programs  and  operaCng  systems:  
§  MulGple  user  programs  
§  OperaGng  system  has  to  orchestrate  them  all    
§ Each  gets  a  share  of  compuGng  cycles  
§  They  may  need  to  share  system  resources  (memory,  I/O,  disks)  
§  Yielding  and  taking  control  of  the  processor  
§  Voluntary  or  “by  force”?  
17  
   
 University  of  Washington  

Course  Outcomes  
¢  FoundaCon:  basics  of  high-­‐level  programming  (Java)  
¢  Understanding  of  some  of  the  abstracCons  that  exist  
between  programs  and  the  hardware  they  run  on,  why  they  
exist,  and  how  they  build  upon  each  other  
¢  Knowledge  of  some  of  the  details  of  underlying  
implementaCons  
¢  Become  more  effecCve  programmers  
§  More  efficient  at  finding  and  eliminaGng  bugs  
§  Understand  some  of  the  many  factors  that  influence  program  
performance  
§  Facility  with  a  couple  more  of  the  many  languages  that  we  use  to  
describe  programs  and  data  
¢  Prepare  for  later  classes  in  CSE  
18  
 University  of  Washington  

Reality  #1:  ints  ≠  integers  &  floats  ≠  reals  

¢  RepresentaCons  are  finite  
¢  Example  1:  Is  x2  ≥  0?  
§  Floats:  Yes!  
§  Ints:  
§   40000  *  40000    -­‐-­‐>  1600000000  
§   50000  *  50000    -­‐-­‐>  ??  
¢  Example  2:  Is  (x  +  y)  +  z    =    x  +  (y  +  z)?  
§  Unsigned  &  Signed  Ints:  Yes!  
§  Floats:    
§   (1e20  +  -­‐1e20)  +  3.14  -­‐-­‐>  3.14  
§   1e20  +  (-­‐1e20  +  3.14)  -­‐-­‐>  ??  

19  
 University  of  Washington  

Reality  #2:  Assembly  sCll  maRers  

¢  Why?  Because  we  want  you  to  suffer?  

20  
 University  of  Washington  

Reality  #2:  Assembly  sCll  maRers  

¢  Chances  are,  you’ll  never  write  a  program  in  assembly  code  
§  Compilers  are  much  beSer  and  more  paGent  than  you  are  
¢  But:  understanding  assembly  is  the  key  to  the  machine-­‐level  
execuCon  model  
§  Behavior  of  programs  in  presence  of  bugs  
§  High-­‐level  language  model  breaks  down  
§  Tuning  program  performance  
§  Understand  opGmizaGons  done/not  done  by  the  compiler  
§  Understanding  sources  of  program  inefficiency  
§  ImplemenGng  system  soQware  
§  OperaGng  systems  must  manage  process  state  
§  FighGng  malicious  soQware  
§  Using  special  units  (Gmers,  I/O  co-­‐processors,  etc.)  inside  processor!  

21  
 University  of  Washington  

Assembly  Code  Example  

¢  Time  Stamp  Counter  
§  Special  64-­‐bit  register  in  Intel-­‐compaGble  machines  
§  Incremented  every  clock  cycle  
§  Read  with  rdtsc  instrucGon  
¢  ApplicaCon  
§  Measure  Gme  (in  clock  cycles)  required  by  procedure  

double t;
start_counter();
P();
t = get_counter();
printf("P required %f clock cycles\n", t);

22  
 University  of  Washington  

Code  to  Read  Counter  

¢  Write  small  amount  of  assembly  code  using  GCC’s  asm  facility  
¢  Inserts  assembly  code  into  machine  code  generated  by  
compiler  
/* Set *hi and *lo (two 32-bit values) to the
high and low order bits of the cycle counter.
*/

void access_counter(unsigned *hi, unsigned *lo)

{
asm("rdtsc; movl %%edx,%0; movl %%eax,%1"
: "=r" (*hi), "=r" (*lo) /* output */
: /* input */
: "%edx", "%eax"); /* clobbered */
}

23  
 University  of  Washington  

Reality  #3:  Memory  MaRers  

¢  So,  what  is  memory?  

24  
 University  of  Washington  

Reality  #3:  Memory  MaRers  

¢  Memory  is  not  unbounded  
§  It  must  be  allocated  and  managed  
§  Many  applicaGons  are  memory-­‐dominated  
¢  Memory  referencing  bugs  are  especially  pernicious  
§  Effects  are  distant  in  both  Gme  and  space  
¢  Memory  performance  is  not  uniform  
§  Cache  and  virtual  memory  effects  can  greatly  affect  program  
performance  
§  AdapGng  program  to  characterisGcs  of  memory  system  can  lead  to  
major  speed  improvements  

25  
 University  of  Washington  

Memory  Referencing  Bug  Example  

double fun(int i)
{
volatile double d[1] = {3.14};
volatile long int a[2];
a[i] = 1073741824; /* Possibly out of bounds */
return d[0];
}

fun(0) –> 3.14

fun(1) –> 3.14
fun(2) –> 3.1399998664856
fun(3) –> 2.00000061035156
fun(4) –> 3.14, then segmentation fault

26  
 University  of  Washington  

Memory  Referencing  Bug  Example  

double fun(int i)
{
volatile double d[1] = {3.14};
volatile long int a[2];
a[i] = 1073741824; /* Possibly out of bounds */
return d[0];
}

fun(0) –> 3.14

fun(1) –> 3.14
fun(2) –> 3.1399998664856
fun(3) –> 2.00000061035156
fun(4) –> 3.14, then segmentation fault

ExplanaCon:   Saved State 4

d7 … d4 3
LocaCon  accessed  by  
d3 … d0 2
fun(i)
a[1] 1
a[0] 0
27  
 University  of  Washington  

Memory  Referencing  Errors  

¢  C  (and  C++)  do  not  provide  any  memory  protecCon  
§  Out  of  bounds  array  references  
§  Invalid  pointer  values  
§  Abuses  of  malloc/free  
¢  Can  lead  to  nasty  bugs  
§  Whether  or  not  bug  has  any  effect  depends  on  system  and  compiler  
§  AcGon  at  a  distance  
§  Corrupted  object  logically  unrelated  to  one  being  accessed  
§  Effect  of  bug  may  be  first  observed  long  aQer  it  is  generated  
¢  How  can  I  deal  with  this?  
§  Program  in  Java  (or  C#,  or  ML,  or  Haskell,  or  Ruby,  or  Racket,  or  …)  
§  Understand  what  possible  interacGons  may  occur  
§  Use  or  develop  tools  to  detect  referencing  errors  
28  
 University  of  Washington  

Memory  System  Performance  Example  

¢  Hierarchical  memory  organizaCon  
¢  Performance  depends  on  access  paRerns  
§  Including  how  program  steps  through  mulG-­‐dimensional  array  

void copyij(int src[2048][2048], void copyji(int src[2048][2048],

int dst[2048][2048]) int dst[2048][2048])
{ {
int i,j; int i,j;
for (i = 0; i < 2048; i++) for (j = 0; j < 2048; j++)
for (j = 0; j < 2048; j++) for (i = 0; i < 2048; i++)
dst[i][j] = src[i][j]; dst[i][j] = src[i][j];
} }

21  Cmes  slower  
(PenCum  4)  
29  
 University  of  Washington  

CSE351’s  role  in  the  CSE  Curriculum  

¢  Pre-­‐requisites  
§  142  and  143:  Intro  Programming  I  and  II  
§  Also  recommended:  390A:  System  and  SoQware  Tools  
¢  One  of  6  core  courses  
§  311:  FoundaGons  of  CompuGng  I  
§  312:  FoundaGons  of  CompuGng  II  
§  331:  SW  Design  and  ImplementaGon  
§  332:  Data  AbstracGons  
§  351:  HW/SW  Interface  
§  352:  HW  Design  and  ImplementaGon  

¢  351  provides  the  context  for  many  follow-­‐on  courses.  

30  
 University  of  Washington  

CSE351’s  place  in  the  CSE  Curriculum  

CSE477/481/490/etc.  
Capstone  and  Project  Courses  

CSE352   CSE333   CSE451   CSE401   CSE461   CSE484   CSE466  

HW  Design   Systems  Prog   Op  Systems   Compilers   Networks   Security   Emb  Systems  

Performance   Distributed   ExecuCon    

Concurrency   Model  
Systems  
Machine  
Comp.  Arch.   Code   Real-­‐Time  
Control  

CSE351   The  HW/SW  Interface:  

underlying  principles  linking  
hardware  and  so3ware  

CS  143  
Intro  Prog  II  

31  
 University  of  Washington  

Course  PerspecCve  
¢  This  course  will  make  you  a  beRer  programmer.  
§  Purpose  is  to  show  how  soQware  really  works  
§  By  understanding  the  underlying  system,  one  can  be  more  effecGve  as  a  
programmer.  
§  BeSer  debugging  
§  BeSer  basis  for  evaluaGng  performance  
§  How  mulGple  acGviGes  work  in  concert  (e.g.,  OS  and  user  programs)  
§  Not  just  a  course  for  dedicated  hackers  
§  What  every  CSE  major  needs  to  know  
§  Job  interviewers  love  to  ask  quesGons  from  351!  
§  Provide  a  context  in  which  to  place  the  other  CSE  courses  you’ll  take  

32  
 University  of  Washington  

Textbooks  
¢  Computer  Systems:  A  Programmer’s  PerspecCve,  2nd  EdiCon  
§  Randal  E.  Bryant  and  David  R.  O’Hallaron    
§  PrenGce-­‐Hall,  2010  
§  hSp://csapp.cs.cmu.edu  
§  This  book  really  maSers  for  the  course!  
§  How  to  solve  labs  
§  PracGce  problems  typical  of  exam  problems  

¢  A  good  C  book  –  any  will  do  

§  The  C  Programming  Language  (Kernighan  and  Ritchie)  
§  C:  A  Reference  Manual  (Harbison  and  Steele)  

33  
 University  of  Washington  

Course  Components  
¢  Lectures  (25)  
§  Introduce  the  concepts;  supplemented  by  textbook  
¢  SecCons  (8+)  
§  Applied  concepts,  important  tools  and  skills  for  labs,  clarificaGon  of  
lectures,  exam  review  and  preparaGon  
¢  WriRen  homework  assignments  (4)  
§  Mostly  problems  from  text  to  solidify  understanding  
¢  Labs  (5,  plus  “lab  0”)  
§  Provide  in-­‐depth  understanding  (via  pracGce)  of  an  aspect  of  system  
¢  Exams  (midterm  +  final)  
§  Test  your  understanding  of  concepts  and  principles  
§  Midterm  currently  scheduled  for  Wednesday,  July  24,  in  class.  
§  Final  is  definitely  Friday,  August  23,  in  class  (last  day).  
¢  Summer  quarter  is  only  9  weeks  long!  
34  
 University  of  Washington  

Resources    
¢  Course  web  page  
§  cs.uw.edu/351  
§  Schedule,  policies,  labs,  homeworks,  and  everything  else  
¢  Course  discussion  board  
§  Keep  in  touch  outside  of  class  –  help  each  other  
§  Staff  will  monitor  and  contribute  
¢  Course  mailing  list  –  check  your  @uw.edu  
§  Low  traffic  –  mostly  announcements;  you  are  already  subscribed  
¢  Office  hours,  appointments,  drop-­‐ins  
§  Poll:  will  be  posted  this  week  
¢  Staff  e-­‐mail:  cse351-­‐staff@cs.washington.edu  
§  Things  that  are  not  appropriate  for  discussion  board  or  beSer  offline  
¢  Anonymous  feedback  
§  Any  comments  about  anything  related  to  the  course  where  you  would  
feel  beSer  not  aSaching  your  name  
35  
 University  of  Washington  

Policies:  Grading  
¢  Exams  (35%):  15%  midterm,  20%  final  
¢  WriRen  assignments  (20%):  weighted  according  to  effort  
§  We’ll  try  to  make  these  about  the  same  
¢  Lab  assignments  (45%):  weighted  according  to  effort  
§  These  will  likely  increase  in  weight  as  the  quarter  progresses  
¢  Late  days:  
§  3  late  days  to  use  as  you  wish  throughout  the  quarter  –  see  website  
¢  CollaboraCon:  
§  hSp://www.cs.washington.edu/educaGon/courses/cse351/13su/
policies.html  
§  hSp://www.cs.washington.edu/students/policies/misconduct  

36  
 University  of  Washington  

Other  details  
¢  Consider  taking  CSE  390A,  1  credit,  useful  skills  
¢  Poll:  office  hours  +  reschedule  secCon  2  (week  of  July  4)  
§  (OH)  Monday  late  morning  /  aQernoon  
§  (OH,  S2)  Tuesday  late  morning  /  aQernoon  
§  (OH,  S2)  Wednesday  late  morning  /  aQernoon  
§  (OH)  Thursday  late  morning  /  aQernoon  
§  (OH,  S2)  Friday  late  morning  /  aQernoon  
¢  Lab  0  due  Friday  5pm.  
§  On  the  website  
§  Non-­‐majors  accounts  
§  CSE  home  VM  
§  Thursday  secGon  on  C  and  tools.  

37  
 University  of  Washington  

Welcome  to  CSE351!  

¢  Let’s  have  fun  
¢  Let’s  learn  –  together  
¢  Let’s  communicate  
¢  Let’s  make  this  a  useful  class  for  all  of  us  
 
¢  Many  thanks  to  the  many  instructors  who  have  shared  their  
lecture  notes  –  I  will  be  borrowing  liberally  through  the  qtr  –  
they  deserve  all  the  credit,  the  errors  are  all  mine  
§  CMU:    Randy  Bryant,  David  O’Halloran,  Gregory  Kesden,  Markus  Püschel  
§  Harvard:  MaS  Welsh  (now  at  Google-­‐SeaSle)  
§  UW:  
Gaetano  Borriello,    Hal  Perkins,  John  Zahorjan,  Peter  Hornyack,  Luis  Ceze  

38