ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo
Pipelining Cache
By Riman Mandal
Contents
? What is Pipelining?
? Cache optimization
? Why Pipelining cache?
? Cache Hit and Cache Access
? How can we implement pipelining to cache
? Cache Pipelining effects
? References
What is Pipelining?
Time
Jobs
24 hrs
24 hrs
24 hrs
Un-pipelined
Throughput Parallelism
1 car /
24 hrs 1
Start and Finish a job before moving to next job
What is Pipelining? (cont.)
Time
Jobs
Throughput Parallelism
1 car / 8
hrs 3
Pipelined Break the job into small stages
Engine1
Engine2
Engine3
Engine4
Body1
Body2
Body2
Body4
Paint1
Paint2
Paint3
Paint4
8 hr
8 hr
8 hr
x3
What is Pipelining? (cont.)
Time
Jobs
3 ns
3 ns
3 ns
Un-pipelined Start and Finish an instruction execution before
moving to next instruction
FET DEC EXE
FET DEC EXE
FET DEC EXE
Cyc 1
Cyc 2
Cyc 3
What is Pipelining? (cont.)
Time
Jobs
Pipelined Break the instruction exeution into small stages
FET IR1
FET IR2
FET IR3
FET IR4
DEC IR1
DEC IR2
DEC IR3
DEC IR4
EXC IR1
EXC IR2
EXC IR3
EXC IR4
Cyc 1
Cyc 2
Cyc 3
1 ns 1 ns 1 ns
Un-pipelined
Clock Speed = 1 / 3ns
= 333 MHz
Pipelined
Clock Speed = 1 / 1ns
= 1 GHz
Cache optimization
? Average memory access time(AMAT) = Hit time + Miss rate ¡Á Miss
penalty
? 5 matrices : hit time, miss rate, miss penalty, bandwidth, power
consumption
? Optimizing CacheAccessTime
¨C Reducing the hit time (1st level catch, way-prediction)
¨C Increasing cache bandwidth (pipelining cache, non-blocking cache, multibanked
cache)
¨C Reducing the miss penalty (critical word first, merging write buffers)
¨C Reducing the miss rate (compiler optimizations)
¨C Reducing the miss penalty or miss rate via parallelism (prefetching)
Why Pipelining Cache?
? Basically used for L1 Cache.
? Multiple Cycles to access the cache
¨C Access comes in cycle N (hit)
¨C Access comes in Cycle N+1 (hit) (Has to wait)
?Hit time = Actual hit time + wait time
Cache Hit and Cache Access
Tag Set Offset@
Tag Data
Tag Data
Tag Data
Set 0
Set 1
Set 2
Hit ?
Hit ?
Hit ?
Where ?
Index
Done
Valid
bit
Designing a 3 Stage pipeline Cache
? Reading the tag and validity bit.
? Combine the result and find out the actual hit and start data read.
? Finishing the data read and transfer data to CPU.
Retrieve tag and valid bit Is Hit? Start data read Serve CPU request
Stage 1:Read tag and valid bit
Tag Set Offset@
Tag Data
Tag Data
Tag Data
Set 0
Set 1
Set 2
Hit ?
Hit ?
Hit ?
Where ?
Index
Done
Valid
bit
Stage 2: If Hit start reading
Tag Set Offset@
Tag Data
Tag Data
Tag Data
Set 0
Set 1
Set 2
Hit ?
Hit ?
Hit ?
Where ?
Index
Done
Valid
bit
Stage 3: Supply data to CPU
Tag Set Offset@
Tag Data
Tag Data
Tag Data
Set 0
Set 1
Set 2
Hit ?
Hit ?
Hit ?
Where ?
Index
Done
Valid
bit
Designing a 2 Stage pipeline Cache
? Checking the tag and validity bit and combine them to find actual hit,
and find the location of data.
? Read data and serve the CPU request.
Retrieve tag and valid bit. Is Hit? Serve CPU request
Example
? Instruction-cache pipeline stages:
¨C Pentium: 1 stage
¨C Pentium Pro through Pentium III: 2 stages
¨C Pentium 4: 4 stages
Pipeline Cache Efficiency
? Increases the bandwidth
? increasing the number of pipeline stages leading to
¨C greater penalty on mispredicted branches
¨C more clock cycles between issuing the load and using the data
Technique
Hit
time
Bandwidth
Miss
penalty
Miss
rate
Power
consumption
Pipelining
Cache
_ +
References
? https://www.udacity.com/course/high-performance-computer-
architecture--ud007
? https://www.youtube.com/watch?v=r9AxfQB_qlc
? ¡°ComputerArchitecture: A Quantitative Approach Fifth Edition¡±, by
Hennessy & Patterson
Ad

Recommended

Relay baton - Good example of one piece continous flow
Relay baton - Good example of one piece continous flow
Tomas Rybing
?
Ensuring QoS in Multi-tenant Hadoop Environments
Ensuring QoS in Multi-tenant Hadoop Environments
Becky Mendenhall
?
Parallel Prime Number Generation Using The Sieve of Eratosthenes
Parallel Prime Number Generation Using The Sieve of Eratosthenes
Adrian-Tudor Panescu
?
Taller syslog
Taller syslog
Alumic S.A
?
Agile processexplained
Agile processexplained
Ashish K Agarwal
?
Quick Sort
Quick Sort
priyankanaidu6
?
¤¬¤ó¤Ð¤ì¥Æ¥Ã¥¯¥ê©`¥É£¡´³±õ¸é´¡Ü¿ÈËÆª£¡£¡
¤¬¤ó¤Ð¤ì¥Æ¥Ã¥¯¥ê©`¥É£¡´³±õ¸é´¡Ü¿ÈËÆª£¡£¡
Yuto Matsukubo
?
A star algorithm in artificial intelligence
A star algorithm in artificial intelligence
Rahul Gupta
?
Pipelining slides
Pipelining slides
PrasantaKumarDash2
?
Coa.ppt2
Coa.ppt2
PrasantaKumarDash2
?
pipelining.pptx
pipelining.pptx
MUNAZARAZZAQELEA
?
Computer-Architechture-Suggesion-book.pdf
Computer-Architechture-Suggesion-book.pdf
ticuhulo
?
Pipelining , structural hazards
Pipelining , structural hazards
Munaam Munawar
?
CPU Pipelining and Hazards - An Introduction
CPU Pipelining and Hazards - An Introduction
Dilum Bandara
?
Concept of Pipelining
Concept of Pipelining
SHAKOOR AB
?
Pipelining 16 computers Artitacher pdf
Pipelining 16 computers Artitacher pdf
MadhuGupta99385
?
Instruction pipelining
Instruction pipelining
Shoaib Commando
?
Introduction_pipeline24.ppt which include
Introduction_pipeline24.ppt which include
GauravDaware2
?
pipelining
pipelining
Siddique Ibrahim
?
Pipelining in computer architecture
Pipelining in computer architecture
Ramakrishna Reddy Bijjam
?
Pipelining
Pipelining
Shubham Bammi
?
Modern processors
Modern processors
gowrivageesan87
?
Pipeline Computing by S. M. Risalat Hasan Chowdhury
Pipeline Computing by S. M. Risalat Hasan Chowdhury
S. M. Risalat Hasan Chowdhury
?
Computer architecture pipelining
Computer architecture pipelining
Mazin Alwaaly
?
week_2Lec02_CS422.pptx
week_2Lec02_CS422.pptx
mivomi1
?
Pipeline Organization Overview and Performance.pdf
Pipeline Organization Overview and Performance.pdf
VenkatesanSatheeswar
?
Sayeh extension(v23)
Sayeh extension(v23)
Farzan Dehbashi
?
pipeline in computer architecture design
pipeline in computer architecture design
ssuser87fa0c1
?
Advanced Token Development - Decentralized Innovation
Advanced Token Development - Decentralized Innovation
arohisinghas720
?
Decipher SEO Solutions for your startup needs.
Decipher SEO Solutions for your startup needs.
mathai2
?

More Related Content

Similar to Pipelining cache (20)

Pipelining slides
Pipelining slides
PrasantaKumarDash2
?
Coa.ppt2
Coa.ppt2
PrasantaKumarDash2
?
pipelining.pptx
pipelining.pptx
MUNAZARAZZAQELEA
?
Computer-Architechture-Suggesion-book.pdf
Computer-Architechture-Suggesion-book.pdf
ticuhulo
?
Pipelining , structural hazards
Pipelining , structural hazards
Munaam Munawar
?
CPU Pipelining and Hazards - An Introduction
CPU Pipelining and Hazards - An Introduction
Dilum Bandara
?
Concept of Pipelining
Concept of Pipelining
SHAKOOR AB
?
Pipelining 16 computers Artitacher pdf
Pipelining 16 computers Artitacher pdf
MadhuGupta99385
?
Instruction pipelining
Instruction pipelining
Shoaib Commando
?
Introduction_pipeline24.ppt which include
Introduction_pipeline24.ppt which include
GauravDaware2
?
pipelining
pipelining
Siddique Ibrahim
?
Pipelining in computer architecture
Pipelining in computer architecture
Ramakrishna Reddy Bijjam
?
Pipelining
Pipelining
Shubham Bammi
?
Modern processors
Modern processors
gowrivageesan87
?
Pipeline Computing by S. M. Risalat Hasan Chowdhury
Pipeline Computing by S. M. Risalat Hasan Chowdhury
S. M. Risalat Hasan Chowdhury
?
Computer architecture pipelining
Computer architecture pipelining
Mazin Alwaaly
?
week_2Lec02_CS422.pptx
week_2Lec02_CS422.pptx
mivomi1
?
Pipeline Organization Overview and Performance.pdf
Pipeline Organization Overview and Performance.pdf
VenkatesanSatheeswar
?
Sayeh extension(v23)
Sayeh extension(v23)
Farzan Dehbashi
?
pipeline in computer architecture design
pipeline in computer architecture design
ssuser87fa0c1
?
Computer-Architechture-Suggesion-book.pdf
Computer-Architechture-Suggesion-book.pdf
ticuhulo
?
Pipelining , structural hazards
Pipelining , structural hazards
Munaam Munawar
?
CPU Pipelining and Hazards - An Introduction
CPU Pipelining and Hazards - An Introduction
Dilum Bandara
?
Concept of Pipelining
Concept of Pipelining
SHAKOOR AB
?
Pipelining 16 computers Artitacher pdf
Pipelining 16 computers Artitacher pdf
MadhuGupta99385
?
Introduction_pipeline24.ppt which include
Introduction_pipeline24.ppt which include
GauravDaware2
?
Computer architecture pipelining
Computer architecture pipelining
Mazin Alwaaly
?
week_2Lec02_CS422.pptx
week_2Lec02_CS422.pptx
mivomi1
?
Pipeline Organization Overview and Performance.pdf
Pipeline Organization Overview and Performance.pdf
VenkatesanSatheeswar
?
pipeline in computer architecture design
pipeline in computer architecture design
ssuser87fa0c1
?

Recently uploaded (20)

Advanced Token Development - Decentralized Innovation
Advanced Token Development - Decentralized Innovation
arohisinghas720
?
Decipher SEO Solutions for your startup needs.
Decipher SEO Solutions for your startup needs.
mathai2
?
Code and No-Code Journeys: The Coverage Overlook
Code and No-Code Journeys: The Coverage Overlook
Applitools
?
Milwaukee Marketo User Group June 2025 - Optimize and Enhance Efficiency - Sm...
Milwaukee Marketo User Group June 2025 - Optimize and Enhance Efficiency - Sm...
BradBedford3
?
ElectraSuite_Prsentation(online voting system).pptx
ElectraSuite_Prsentation(online voting system).pptx
mrsinankhan01
?
Smadav Pro 2025 Rev 15.4 Crack Full Version With Registration Key
Smadav Pro 2025 Rev 15.4 Crack Full Version With Registration Key
joybepari360
?
Migrating to Azure Cosmos DB the Right Way
Migrating to Azure Cosmos DB the Right Way
Alexander (Alex) Komyagin
?
Complete WordPress Programming Guidance Book
Complete WordPress Programming Guidance Book
Shabista Imam
?
MOVIE RECOMMENDATION SYSTEM, UDUMULA GOPI REDDY, Y24MC13085.pptx
MOVIE RECOMMENDATION SYSTEM, UDUMULA GOPI REDDY, Y24MC13085.pptx
Maharshi Mallela
?
A Guide to Telemedicine Software Development.pdf
A Guide to Telemedicine Software Development.pdf
Olivero Bozzelli
?
Women in Tech: Marketo Engage User Group - June 2025 - AJO with AWS
Women in Tech: Marketo Engage User Group - June 2025 - AJO with AWS
BradBedford3
?
Reimagining Software Development and DevOps with Agentic AI
Reimagining Software Development and DevOps with Agentic AI
Maxim Salnikov
?
Async-ronizing Success at Wix - Patterns for Seamless Microservices - Devoxx ...
Async-ronizing Success at Wix - Patterns for Seamless Microservices - Devoxx ...
Natan Silnitsky
?
Modern Platform Engineering with Choreo - The AI-Native Internal Developer Pl...
Modern Platform Engineering with Choreo - The AI-Native Internal Developer Pl...
WSO2
?
Automated Migration of ESRI Geodatabases Using XML Control Files and FME
Automated Migration of ESRI Geodatabases Using XML Control Files and FME
Safe Software
?
Best MLM Compensation Plans for Network Marketing Success in 2025
Best MLM Compensation Plans for Network Marketing Success in 2025
LETSCMS Pvt. Ltd.
?
Emvigo Capability Deck 2025: Accelerating Innovation Through Intelligent Soft...
Emvigo Capability Deck 2025: Accelerating Innovation Through Intelligent Soft...
Emvigo Technologies
?
Shell Skill Tree - LabEx Certification (LabEx)
Shell Skill Tree - LabEx Certification (LabEx)
VICTOR MAESTRE RAMIREZ
?
Software Testing & it¡¯s types (DevOps)
Software Testing & it¡¯s types (DevOps)
S Pranav (Deepu)
?
How to Choose the Right Web Development Agency.pdf
How to Choose the Right Web Development Agency.pdf
Creative Fosters
?
Advanced Token Development - Decentralized Innovation
Advanced Token Development - Decentralized Innovation
arohisinghas720
?
Decipher SEO Solutions for your startup needs.
Decipher SEO Solutions for your startup needs.
mathai2
?
Code and No-Code Journeys: The Coverage Overlook
Code and No-Code Journeys: The Coverage Overlook
Applitools
?
Milwaukee Marketo User Group June 2025 - Optimize and Enhance Efficiency - Sm...
Milwaukee Marketo User Group June 2025 - Optimize and Enhance Efficiency - Sm...
BradBedford3
?
ElectraSuite_Prsentation(online voting system).pptx
ElectraSuite_Prsentation(online voting system).pptx
mrsinankhan01
?
Smadav Pro 2025 Rev 15.4 Crack Full Version With Registration Key
Smadav Pro 2025 Rev 15.4 Crack Full Version With Registration Key
joybepari360
?
Complete WordPress Programming Guidance Book
Complete WordPress Programming Guidance Book
Shabista Imam
?
MOVIE RECOMMENDATION SYSTEM, UDUMULA GOPI REDDY, Y24MC13085.pptx
MOVIE RECOMMENDATION SYSTEM, UDUMULA GOPI REDDY, Y24MC13085.pptx
Maharshi Mallela
?
A Guide to Telemedicine Software Development.pdf
A Guide to Telemedicine Software Development.pdf
Olivero Bozzelli
?
Women in Tech: Marketo Engage User Group - June 2025 - AJO with AWS
Women in Tech: Marketo Engage User Group - June 2025 - AJO with AWS
BradBedford3
?
Reimagining Software Development and DevOps with Agentic AI
Reimagining Software Development and DevOps with Agentic AI
Maxim Salnikov
?
Async-ronizing Success at Wix - Patterns for Seamless Microservices - Devoxx ...
Async-ronizing Success at Wix - Patterns for Seamless Microservices - Devoxx ...
Natan Silnitsky
?
Modern Platform Engineering with Choreo - The AI-Native Internal Developer Pl...
Modern Platform Engineering with Choreo - The AI-Native Internal Developer Pl...
WSO2
?
Automated Migration of ESRI Geodatabases Using XML Control Files and FME
Automated Migration of ESRI Geodatabases Using XML Control Files and FME
Safe Software
?
Best MLM Compensation Plans for Network Marketing Success in 2025
Best MLM Compensation Plans for Network Marketing Success in 2025
LETSCMS Pvt. Ltd.
?
Emvigo Capability Deck 2025: Accelerating Innovation Through Intelligent Soft...
Emvigo Capability Deck 2025: Accelerating Innovation Through Intelligent Soft...
Emvigo Technologies
?
Shell Skill Tree - LabEx Certification (LabEx)
Shell Skill Tree - LabEx Certification (LabEx)
VICTOR MAESTRE RAMIREZ
?
Software Testing & it¡¯s types (DevOps)
Software Testing & it¡¯s types (DevOps)
S Pranav (Deepu)
?
How to Choose the Right Web Development Agency.pdf
How to Choose the Right Web Development Agency.pdf
Creative Fosters
?
Ad

Pipelining cache

  • 2. Contents ? What is Pipelining? ? Cache optimization ? Why Pipelining cache? ? Cache Hit and Cache Access ? How can we implement pipelining to cache ? Cache Pipelining effects ? References
  • 3. What is Pipelining? Time Jobs 24 hrs 24 hrs 24 hrs Un-pipelined Throughput Parallelism 1 car / 24 hrs 1 Start and Finish a job before moving to next job
  • 4. What is Pipelining? (cont.) Time Jobs Throughput Parallelism 1 car / 8 hrs 3 Pipelined Break the job into small stages Engine1 Engine2 Engine3 Engine4 Body1 Body2 Body2 Body4 Paint1 Paint2 Paint3 Paint4 8 hr 8 hr 8 hr x3
  • 5. What is Pipelining? (cont.) Time Jobs 3 ns 3 ns 3 ns Un-pipelined Start and Finish an instruction execution before moving to next instruction FET DEC EXE FET DEC EXE FET DEC EXE Cyc 1 Cyc 2 Cyc 3
  • 6. What is Pipelining? (cont.) Time Jobs Pipelined Break the instruction exeution into small stages FET IR1 FET IR2 FET IR3 FET IR4 DEC IR1 DEC IR2 DEC IR3 DEC IR4 EXC IR1 EXC IR2 EXC IR3 EXC IR4 Cyc 1 Cyc 2 Cyc 3 1 ns 1 ns 1 ns Un-pipelined Clock Speed = 1 / 3ns = 333 MHz Pipelined Clock Speed = 1 / 1ns = 1 GHz
  • 7. Cache optimization ? Average memory access time(AMAT) = Hit time + Miss rate ¡Á Miss penalty ? 5 matrices : hit time, miss rate, miss penalty, bandwidth, power consumption ? Optimizing CacheAccessTime ¨C Reducing the hit time (1st level catch, way-prediction) ¨C Increasing cache bandwidth (pipelining cache, non-blocking cache, multibanked cache) ¨C Reducing the miss penalty (critical word first, merging write buffers) ¨C Reducing the miss rate (compiler optimizations) ¨C Reducing the miss penalty or miss rate via parallelism (prefetching)
  • 8. Why Pipelining Cache? ? Basically used for L1 Cache. ? Multiple Cycles to access the cache ¨C Access comes in cycle N (hit) ¨C Access comes in Cycle N+1 (hit) (Has to wait) ?Hit time = Actual hit time + wait time
  • 9. Cache Hit and Cache Access Tag Set Offset@ Tag Data Tag Data Tag Data Set 0 Set 1 Set 2 Hit ? Hit ? Hit ? Where ? Index Done Valid bit
  • 10. Designing a 3 Stage pipeline Cache ? Reading the tag and validity bit. ? Combine the result and find out the actual hit and start data read. ? Finishing the data read and transfer data to CPU. Retrieve tag and valid bit Is Hit? Start data read Serve CPU request
  • 11. Stage 1:Read tag and valid bit Tag Set Offset@ Tag Data Tag Data Tag Data Set 0 Set 1 Set 2 Hit ? Hit ? Hit ? Where ? Index Done Valid bit
  • 12. Stage 2: If Hit start reading Tag Set Offset@ Tag Data Tag Data Tag Data Set 0 Set 1 Set 2 Hit ? Hit ? Hit ? Where ? Index Done Valid bit
  • 13. Stage 3: Supply data to CPU Tag Set Offset@ Tag Data Tag Data Tag Data Set 0 Set 1 Set 2 Hit ? Hit ? Hit ? Where ? Index Done Valid bit
  • 14. Designing a 2 Stage pipeline Cache ? Checking the tag and validity bit and combine them to find actual hit, and find the location of data. ? Read data and serve the CPU request. Retrieve tag and valid bit. Is Hit? Serve CPU request
  • 15. Example ? Instruction-cache pipeline stages: ¨C Pentium: 1 stage ¨C Pentium Pro through Pentium III: 2 stages ¨C Pentium 4: 4 stages
  • 16. Pipeline Cache Efficiency ? Increases the bandwidth ? increasing the number of pipeline stages leading to ¨C greater penalty on mispredicted branches ¨C more clock cycles between issuing the load and using the data Technique Hit time Bandwidth Miss penalty Miss rate Power consumption Pipelining Cache _ +
  • 17. References ? https://www.udacity.com/course/high-performance-computer- architecture--ud007 ? https://www.youtube.com/watch?v=r9AxfQB_qlc ? ¡°ComputerArchitecture: A Quantitative Approach Fifth Edition¡±, by Hennessy & Patterson