Велике идеје

• Фамилија рачунара
• IBM System/360 1964
• DEC PDP-8
• Идеја раздвајања архитектуре од имплементације
• Microporgrammed control unit
• Wilkes 1951
• IBM S/360 1964
• Cache меморија
• IBM S/360 model 85 1969

​

Велике идеје

• Solid State RAM
• Уместо језгара
• Микропроцесор
• Intel 4004 1971
• Pipelining
• Паралелизам у fetch execute cycle
• Више процесора

​

Следећа велика идеја- RISC

• Reduced Instruction Set Computer

​

• особине
• Много general purpose регистара
• Или компајлер оптимизује број регистара
• Прост скуп инструкција
• Оптимизација instruction pipeline-а

​

Поређење

CISC

• Трошкови софтвера већи од трошкова хардвера
• Језиви вишег нивоа компликовани
• Тешко учење, хардвер и софтвер се раздвајају неприродно
• Добије се:
• Велики скупови инструкција
• Више адресних система
• Хардверска имплементација структура програма
• Пример CASE (switch) на VAX-у

Идеја CISC-а

• Лако писање компајлера
• Ефикасно извршење
• Complex operations in microcode
• Подршка још сложенијим језицима ВН

Особине циклуса извршења

• Експерименти
• Много операнада
• Много циклсуа извршења
• Много гранања
• Сложене операције

​

• Резултати:

Weighted Relative Dynamic Frequency of HLL Operations [PATT82a]

Операнди

• Углавном локалне варијабле, скалари
• Дакле, фокус на дохватање локалних варијабли!

​

Позивање процедура

• Троши време
• Зависи од броја параметара
• Зависи од дубине петљи
• Статистика: ретко!
• Варијабле су локалне
• (locality of reference)

Импликације

• Оптимизовати операције које су најчешће и које троше највише времена
• Много регистара
• За дохват операнада
• Посебан фокус на проточну обраду
• Предвиђање гранања
• И: reduced instruction set

​

Шта су велики регистри?

• Software
• Компајлер алоцира регистре
• Критеријум: најчешће коришћени
• Захтевна анализа
• Hardware
• Више физичких регистара
• Више варијабли је у регистрима

Регистри за локалне варијабле

• Локални скалари у регистре!
• Позиви у РАМ смањени
• Позив потпрограма руши локалност!
• Параметри се шаљу
• Резултати се враћају!
• Поновно креирање варијабли!

Register Windows

• Мало параметара
• Ограничен начин позивања из ПП

​

Overlapping Register Windows

Circular Buffer diagram

Кружни бафер

• Код позива у бафер, тренутни window pointer помера се на тренутно активан register window
• Ако су сви прозори употребљени, генерише се interrupt и најстарији прозор иде у меморију
• Сачувани window pointer показује где се позива сачувани прозор

​

Глобалне варијабле

• Такође им дајемо посебан скуп регистара

Регистри и Cache

Referencing a Scalar - �Window Based Register File

Referencing a Scalar - Cache

Compiler Based Register Optimization

• Assume small number of registers (16-32)
• Optimizing use is up to compiler
• HLL programs have no explicit references to registers
• usually - think about C - register int
• Assign symbolic or virtual register to each candidate variable
• Map (unlimited) symbolic registers to real registers
• Symbolic registers that do not overlap can share real registers
• If you run out of real registers some variables use memory

Graph Coloring

• Given a graph of nodes and edges
• Assign a color to each node
• Adjacent nodes have different colors
• Use minimum number of colors
• Nodes are symbolic registers
• Two registers that are live in the same program fragment are joined by an edge
• Try to color the graph with n colors, where n is the number of real registers
• Nodes that can not be colored are placed in memory

Graph Coloring Approach

Why CISC (1)?

• Compiler simplification?
• Disputed…
• Complex machine instructions harder to exploit
• Optimization more difficult
• Smaller programs?
• Program takes up less memory but…
• Memory is now cheap
• May not occupy less bits, just look shorter in symbolic form
• More instructions require longer op-codes
• Register references require fewer bits

​

​

​

Why CISC (2)?

• Faster programs?
• Bias towards use of simpler instructions
• More complex control unit
• Microprogram control store larger
• thus simple instructions take longer to execute

​

• It is far from clear that CISC is the appropriate solution

​

RISC Characteristics

• One instruction per cycle
• Register to register operations
• Few, simple addressing modes
• Few, simple instruction formats
• Hardwired design (no microcode)
• Fixed instruction format
• More compile time/effort

RISC v CISC

• Not clear cut
• Many designs borrow from both philosophies
• e.g. PowerPC and Pentium II

RISC Pipelining

• Most instructions are register to register
• Two phases of execution
• I: Instruction fetch
• E: Execute
• ALU operation with register input and output
• For load and store
• I: Instruction fetch
• E: Execute
• Calculate memory address
• D: Memory
• Register to memory or memory to register operation

Effects of Pipelining

Optimization of Pipelining

• Delayed branch
• Does not take effect until after execution of following instruction
• This following instruction is the delay slot
• Delayed Load
• Register to be target is locked by processor
• Continue execution of instruction stream until register required
• Idle until load complete
• Re-arranging instructions can allow useful work whilst loading
• Loop Unrolling
• Replicate body of loop a number of times
• Iterate loop fewer times
• Reduces loop overhead
• Increases instruction parallelism
• Improved register, data cache or TLB locality

Loop Unrolling Twice �Example

do i=2, n-1

a[i] = a[i] + a[i-1] * a[i+l]

end do

​

Becomes

​

do i=2, n-2, 2

a[i] = a[i] + a[i-1] * a[i+i]

a[i+l] = a[i+l] + a[i] * a[i+2]

end do

if (mod(n-2,2) = i) then

a[n-1] = a[n-1] + a[n-2] * a[n]

end if

​

Normal and Delayed Branch

Use of Delayed �Branch

Controversy

• Quantitative
• compare program sizes and execution speeds
• Qualitative
• examine issues of high level language support and use of VLSI real estate
• Problems
• No pair of RISC and CISC that are directly comparable
• No definitive set of test programs
• Difficult to separate hardware effects from complier effects
• Most comparisons done on “toy” rather than production machines
• Most commercial devices are a mixture

Required Reading

• Stallings chapter 13
• Manufacturer web sites

MIPS

MIPS

The instruction set consists of a variety of basic instructions, including:

• 21 arithmetic instructions (+, -, *, /, %)
• 8 logic instructions (&, |, ~)
• 8 bit manipulation instructions
• 12 comparison instructions (>, <, =, >=, <=, ¬)
• 25 branch/jump instructions
• 15 load instructions
• 10 store instructions
• 8 move instructions
• 4 miscellaneous instructions

​

RISC pipeline

RISC Pipelines�

• fetch instructions from memory
• read registers and decode the instruction
• execute the instruction or calculate an address
• access an operand in data memory
• write the result into a register

​

CISC

MULT 2:3, 5:2

RISC

LOAD A, 2:3�LOAD B, 5:2�PROD A, B�STORE 2:3, A

Разлика у приступу смањењу времена обраде

CISC

RISC