2/15/11%1%CS%61C:%Great%Ideas%in%Computer%Architecture%(Machine%Structures)%Instructors:%Randy%H.%Katz%David%A.%PaGerson%hGp://inst.eecs.Berkeley.edu/~cs61c/fa10%1%Spring%2010%OO%Lecture%#9%2/15/11%NewOSchool%Machine%Structures%(It’s%a%bit%more%complicated!)%• Parallel%Requests%Assigned%to%computer%e.g.,%Search%“Katz”%• Parallel%Threads%Assigned%to%core%e.g.,%Lookup,%Ads%• Parallel%Instruc]ons%>1%instruc]on%@%one%]me%e.g.,%5%pipelined%instruc]ons%• Parallel%Data%>1%data%item%@%one%]me%e.g.,%Add%of%4%pairs%of%words%• Hardware%descrip]ons%All%gates%@%one%]me%2/15/11% Spring%2010%OO%Lecture%#9% 3%Smart%Phone%Warehouse%Scale%Computer%So#ware((((((((Hardware(Harness(Parallelism(&(Achieve(High(Performance(Logic%Gates%Core% Core%…%%%%%%Memory%%%%%%%%%%%%%%%(Cache)%Input/Output%Computer%Main%Memory%Core%%%%%%%%%%Instruc]on%Unit(s)%%%%%%%%Func]onal%Unit(s)%A3+B3%A2+B2%A1+B1%A0+B0%Today’s%Lecture%Levels%of%Representa]on/Interpreta]on%lw %%%$t0,%0($2)%lw %%%$t1,%4($2)%sw %%%$t1,%0($2)%sw %%%$t0,%4($2)%High%Level%Language%Program%(e.g.,%C)%Assembly%%Language%Program%(e.g.,%MIPS)%Machine%%Language%Program%(MIPS)%Hardware%Architecture%DescripCon%(e.g.,%block%diagrams)%%Compiler)Assembler)Machine)Interpreta4on)temp%=%v[k];%v[k]%=%v[k+1];%v[k+1]%=%temp;%0000 1001 1100 0110 1010 1111 0101 1000 1010 1111 0101 1000 0000 1001 1100 0110 1100 0110 1010 1111 0101 1000 0000 1001 0101 1000 0000 1001 1100 0110 1010 1111 !Logic%Circuit%DescripCon%(Circuit%SchemaCc%Diagrams)%Architecture)Implementa4on)Anything%can%be%represented%as%a%number,%%i.e.,%data%or%instruc]ons%2/15/11% 4%Spring%2010%OO%Lecture%#9%Today’s%Lecture%Review%• Everything%is%a%(binary)%number%in%a%computer%– Instruc]ons%and%data;%stored%program%concept%• Assemblers%can%enhance%machine%instruc]on%set%to%help%assemblyOlanguage%programmer%• Translate%from%text%that%easy%for%programmers%to%understand%into%code%that%machine%executes%efficiently:%Compilers,%Assemblers%• Linkers%allow%separate%transla]on%of%modules%2/15/11% Spring%2010%OO%Lecture%#9% 5%Agenda%• Compilers,%Op]miza]on,%Interpreters,%JustOInOTime%Compiler%• Administrivia%• Dynamic%Linking%• Techno logy%Trends%Revisited%• Technology%Break%• Components%of%a%Computer%2/15/11% Spring%2010%OO%Lecture%#9% 6%7%What’s%a%Compiler?%• Compiler:%a%program%that%accepts%as%input%a%program%text%in%a%certain%language%and%produces%as%output%a%program%text%in%another%language,%while(preserving(the(meaning(of(that(text.%• The%text%must%comply%with%the%syntax%rules%of%whichever%programming%language%it%is%wriGen%in.%%• A%compiler's%complexity%depends%on%the%syntax%of%the%language%and%how%much%abstrac]on%that%programming%language%provides.%%– A%C%compiler%is%much%simpler%than%C++%Compiler%• Compiler%executes%before(compiled%program%runs%2/15/11% Spring%2010%OO%Lecture%#9%2/15/11%2%2O8%Compiled%Languages:%EditOCompileOLinkORun%Editor% Source code%Compiler% Object code%Linker% Executable program%Editor% Source code%Compiler% Object code%Editor% Source code%Compiler% Object code%%2/15/11% Spring%2010%OO%Lecture%#9%Compiler%Op]miza]on%• gcc%compiler%op]ons%OO1:%the%compiler%tries%to%reduce%code%size%and%execu]on%]me,%without%performing%any%op]miza]ons%that%take%a%great%deal%of%compila]on%]me%OO2:%Op]mize%even%more.%GCC%performs%nearly%all%supported%op]miza]ons%that%do%not%involve%a%spaceOspeed%tradeoff.%As%compared%to%OO,%this%op]on%increases%both%compila]on%]me%and%the%performance%of%the%generated%code%OO3:%Op]mize%yet%more.%All%OO2%op]miza]ons%and%also%turns%on%the%OfinlineOfunc]ons,%…%2/15/11% Spring%2010%OO%Lecture%#9% 9%What%is%Typical%Benefit%of%%Compiler%Op]miza]on?%• What%is%a%typical%program?%• For%now,%try%a%toy%program:%%%BubbleSort.c%#define%ARRAY_SIZE%20000%int%main()%{%%%int%iarray[ARRAY_SIZE],%x,%y,%holder; %%for(x%=%0;%x%<%ARRAY_SIZE;%x++)%%%%%for(y%=%0;%y%<%ARRAY_SIZEO1;%y++)%%%%%%%if(iarray[y]%>%iarray[y+1])%{%%%%%%%%%holder%=%iarray[y+1];%%%%%%%%%iarray[y+1]%=%iarray[y];%%%%%%%%%iarray[y]%=%holder;%%%%%%%}%}%2/15/11% Spring%2010%OO%Lecture%#9% 10%Unop]mized%MIPS%Code%$L3:%%%%%%%%%lw%%%%%%$2,80016($sp)%%%%%%%%%slt%%%%%$3,$2,20000%%%%%%%%%bne%%%%%$3,$0,$L6%%%%%%%%%j%%%%%%%$L4%$L6:%%%%%%%%%.set%%%%noreorder%%%%%%%%%nop%%%%%%%%%.set%%%%reorder%%%%%%%%%sw%%%%%%$0,80020($sp)%$L7:%%%%%%%%%lw%%%%%%$2,80020($sp)%%%%%%%%%slt%%%%%$3,$2,19999%%%%%%%%%bne%%%%%$3,$0,$L10%%%%%%%%%j%%%%%%%$L5%$L10:%%%%%%%%%lw%%%%%%$2,80020($sp)%%%%%%%%%move%%%%$3,$2%%%%%%%%%sll%%%%%$2,$3,2%%%%%%%%%addu%%%%$3,$sp,16%2/15/11% Spring%2010%OO%Lecture%#9% 11%%%%%%%%addu%%%%$2,$3,$2%%%%%%%%%lw%%%%%%$4,80020($sp)%%%%%%%%%addu%%%%$3,$4,1%%%%%%%%%move%%%%$4,$3%%%%%%%%%sll%%%%%$3,$4,2%%%%%%%%%addu%%%%$4,$sp,16%%%%%%%%%addu%%%%$3,$4,$3%%%%%%%%%lw%%%%%%$2,0($2)%%%%%%%%%lw%%%%%%$3,0($3)%%%%%%%%%slt%%%%%$2,$3,$2%%%%%%%%%beq%%%%%$2,$0,$L9%%%%%%%%%lw%%%%%%$3,80020($sp)%%%%%%%%%addu%%%%$2,$3,1%%%%%%%%%move%%%%$3,$2%%%%%%%%sll%%%%%$2,$3,2%%%%%%%%%addu%%%%$3,$sp,16%%%%%%%%%addu%%%%$2,$3,$2%%%%%%%%%lw%%%%%%$3,0($2)%%%%%%%%%sw%%%%%%$3,80024($sp%%%%lw%%%%%%$3,80020($sp)%%%%%%%%%addu%%%%$2,$3,1%%%%%%%%%move%%%%$3,$2%%%%%%%%%sll%%%%%$2,$3,2%%%%%%%%%addu%%%%$3,$sp,16%%%%%%%%%addu%%%%$2,$3,$2%%%%%%%%%lw%%%%%%$3,80020($sp)%%%%%%%%%move%%%%$4,$3%%%%%%%%%sll%%%%%$3,$4,2%%%%%%%%%addu%%%%$4,$sp,16%%%%%%%%%addu%%%%$3,$4,$3%%%%%%%%%lw%%%%%%$4,0($3)%%%%%%%%%sw%%%%%%$4,0($2)%%%%%%%%%lw%%%%%%$2,80020($sp)%%%%%%%%move%%%%$3,$2%%%%%%%%%sll%%%%%$2,$3,2%%%%%%%%%addu%%%%$3,$sp,16%%%%%%%%%addu%%%%$2,$3,$2%%%%%%%%%lw%%%%%%$3,80024($sp)%%%%%%%%%sw%%%%%%$3,0($2)%$L11:%$L9:%%%%%%%%%lw%%%%%%$2,80020($sp)%%%%%%%%%addu%%%%$3,$2,1%%%%%%%%%sw%%%%%%$3,80020($sp)%%%%%%%%%j%%%%%%%$L7%$L8:%$L5:%%%%%%%%%lw%%%%%%$2,80016($sp)%%%%%%%%%addu%%%%$3,$2,1%%%%%%%%%sw%%%%%%$3,80016($sp)%%%%%%%%%j%%%%%%%$L3%$L4:%$L2:%%%%%%%%%li%%%%%%$12,65536%%%%%%%%%ori%%%%%$12,$12,0x38b0%%%%%%%%%addu%%%%$13,$12,$sp%%%%%%%%%addu%%%%$sp,$sp,$12%%%%%%%%%j%%%%%%%$31%OO2%op]mized%MIPS%Code%%li%%%%%%$13,65536%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ori%%%%%$13,$13,0x3890%%%%%%%%%addu%%%%$13,$13,$sp%%%%%%%%%sw%%%%%%$28,0($13)%%%%%%%%%move%%%%$4,$0%%%%%%%%%addu%%%%$8,$sp,16%$L6:%%%%%%%%%move%%%%$3,$0%%%%%%%%%addu%%%%$9,$4,1%%%%%%%%%.p2align%3%$L10:%%%%%%%%%sll%%%%%$2,$3,2%%%%%%%%%addu%%%%$6,$8,$2%%%%%%%%%addu%%%%$7,$3,1%%%%%%%%%sll%%%%%$2,$7,2%%%%%%%%%addu%%%%$5,$8,$2%%%%%%%%%lw%%%%%%$3,0($6)%%%%%%%%%lw%%%%%%$4,0($5)%2/15/11% Spring%2010%OO%Lecture%#9%
View Full Document