Neowiz Holdings Corporation · KRX:042420
Neowiz — Technical Presentation (2003)
30 slides from Neowiz's technical presentation, 2003
Slide 1: Low-Level Optimizations in the PowerPC/Linux Kernels
Low-Level Optimizations in the PowerPC/Linux Kernels Dr. Paul Mackerras Senior Technical Staff Member IBM Linux Technology Center OzLabs Canberra, Australia paulus@samba.org paulus@au1.ibm.com
Slide 2: Outline
Outline Introduction PowerPC® architecture and implementations Optimization techniques: profiling and benchmarking Instruction cache coherence Memory copying PTE management Conclusions
Slide 3: PowerPC Architecture
PowerPC Architecture PowerPC = “POWER Performance Computing” POWER = “Performance Optimization with Enhanced RISC” PowerPC is a specification for an Instruction Set Architecture Specifies registers, instructions, encodings, etc. RISC load/store architecture 32 general-purpose registers, 2 data addre
Slide 4: PowerPC Architecture: Caches
PowerPC Architecture Caches Instruction and data caches may be separate Instructions provided for cache management dcbst: Data cache block store dcbf/dcbi: Data cache block flush/invalidate icbi: Instruction cache block invalidate Instruction cache is not required to snoop Hardware does not maintain
Slide 5: PowerPC Architecture: Memory management
PowerPC Architecture Memory management Architecture specifies hashed page table structure. Implemented in desktop/server CPUs 4kB pages; POWER4TM also has 16MB pages One hash table for all processes + kernel Process “effective” addresses are translated to “virtual” addresses using segment table 256M
Slide 6: PowerPC Implementations
PowerPC Implementations 32-bit implementations: IBM and Motorola Desktop/server: 601, 604, 750 (Apple G3), 74xx (Apple G4) ® Used in Apple machines, previous IBM RS/6000 machines, and embedded applications Embedded: IBM 4xx series, Motorola 8xx series 64-bit implementations: IBM POWER3TM: designed f
Slide 7: Optimizing the kernel
Optimizing the kernel Want the kernel to go faster How do we know what to change? Profiling: where is the kernel spending most of its time? Micro-benchmarks: what operations are particularly slow? Code inspection + intuition: what code looks slow? often unreliable How do we know if our changes have
Slide 8: Profiling
Profiling Measures the time spent in individual kernel routines Periodically sample next instruction pointer Can use timer interrupt or other periodic interrupt Construct histogram Map NIP to bucket index, increment bucket Postprocessing: map histogram buckets to routines Limitations Sampling leads
Slide 9: Benchmarks
Benchmarks Micro-benchmarks Measure speed of individual kernel operations LMBenchTM Well-known suite written originally by Larry McVoy Application-level benchmarks Run some specific user-level application and measure how long it takes Many exist, both proprietary and open-source Kernel compile Ensur
Slide 10: Test systems
Apple PowerBook® G3 laptop 400MHz PowerPC 750TM processor (32-bit) 32kB I + 32kB D L1 cache, 1MB L2 cache, 192MB RAM IBM® pSeriesTM model 650 server Eight 1.45GHz POWER4+ processors (64-bit) 64kB I + 32kB D L1 cache per cpu, 1.5MB L2 cache per 2 cpus, 8GB RAM IBM “Walnut” embedded evaluation board 2
Slide 11: Cache flushing
Cache flushing Userspace expects kernel to maintain I-cache coherence for pages mapped into user processes Pages mapped from files Pages copied on write (private mappings, fork) Zeroed pages Flush sequence: flush_dcache_icache() one dcbst per cache line one icbi per cache line Only required after pa
Slide 12: Original approach
Original approach Use flush_page_to_ram hook in MM subsystem Called whenever user page mapping is established. Profile results (G3 PowerBook, kernel compile) flush_dcache_icache 6763 ppc6xx_idle 2238 do_page_fault 857 copy_page 537 clear_page 523 copy_tofrom_user 356 do_no_page 231 add_hash_page 220
Slide 13: Optimized approach
Optimized approach Record I-cache state for each page PG_arch_1 bit in page_struct structure Cleared when page is allocated Set after flush is done Flush in update_mmu_cache Only if PG_arch_1 bit is clear Clear PG_arch_1 in flush_dcache_page Called when kernel modifies a page Scheme suggested by Dav
Slide 14: Optimized approach – results
Optimized approach – results Profile results (G3 PowerBook, kernel compile) Routine Original Optimized flush_dcache_icache 6763 2974 ppc6xx_idle 2238 2468 do_page_fault 857 667 copy_page 537 390 clear_page 523 509 copy_tofrom_user 356 299 do_no_page 231 129 add_hash_page 220 92 flush_hash_page 195 1
Slide 15: Optimized approach – results
Optimized approach – results LMBench results (excerpt) Host OS Mhz fork exec sh proc proc proc --------- ------------- ---- ---- ---- ---- argo Linux 2.5.66 400 795. 5065 23.K argo Linux 2.5.66 400 659. 2254 11.K 1 0.5 Original Optimized 0 Fork Exec Shell
Slide 16: Further Optimization
Further Optimization Why are we still flushing so much? Page cache pages – flushing eliminated in steady state Copy-on-write pages – may contain instructions Zero pages – don't want to leak data through Icache Most COW or zero pages will never be executed Can defer flush if we have per-page execute
Slide 17: Further optimization: results
Further optimization: results PPC405 embedded processor Kernel compile System time reduced 5.9% Overall time reduced 0.37% Profile: flush_dcache_icache hits reduced from 1685 to 31 Floating-point emulation code is the most time-consuming
Slide 18: Memory copying
Memory copying To/from user process space: copy_tofrom_user() Used for read, write, and many other system calls Copying pages, e.g. copy-on-write faults: copy_page() Copying kernel data structures: memcpy() copy_page and copy_tofrom_user are #4 and #6 in the profile for a kernel compile (G3 PowerBoo
Slide 19: Memory copy techniques
Memory copy techniques Optimum memory copy routine depends on many factors. Speed of unaligned accesses Storage hierarchy – number of levels and latency Automatic hardware prefetch mechanisms Cache prefetch instructions Load-to-use penalty Out-of-order instruction execution capability Penalty for co
Slide 20: Memory copy techniques
Memory copy techniques Optimum routine also depends on: Size and alignment of regions to be copied Aggressive loop unrolling may only help large copies Whether the source or destination are present in cache Extended instruction sets may only help if data is in cache Statistics for 64-bit kernel (POW
Slide 21: POWER4-optimized memory copy
POWER4-optimized memory copy Two separate routines. Small copy handles arbitrary alignment, optimized for small copies. Used for memcpy() and most copy_tofrom_user() Page copy assumes cacheline aligned, 1 page copy Used for copy_page() and page-sized and aligned copy_tofrom_user() copy_tofrom_user()
Slide 22: POWER4-optimized small copy
POWER4-optimized small copy Initially copy 1-7 bytes to get destination address 8-byte aligned Check whether source address is 8-byte aligned and branch to one of 2 copy loops: Source aligned: 2 loads, 2 stores per iteration (16 bytes) Source unaligned: 2 loads, 4 shifts, 2 ORs, 2 stores per iterati
Slide 23: POWER4-optimized page copy
POWER4-optimized page copy POWER4 architecture details: Stores go through to level 2 cache L2 cache is organized as 3 interleaved banks Optimum order of stores is to store into each bank in turn. Highest bandwidth page copy procedure: Main loop copies 6 cache lines in interleaved fashion 3 blocks of
Slide 24: Optimized memory copy: results
Optimized memory copy: results Selected LMBench results: 1500 1334 1250 Bandwidth (MB/s) 1000 903 823 832 750 557 557 500 444 419 250 0 Pipe Unix TCP File reread socket socket
Slide 25: Optimized memory copy: results
Optimized memory copy: results Kernel compile: System time reduced from 8.30 to 8.19 seconds (1.3%) Overall time reduced by 0.13%. Improvement is very modest but still worthwhile.
Slide 26: PTE Management
PTE Management Hardware uses a hash table for storing page table entries (PTEs) Linux memory management (MM) subsystem uses a 3- level tree (on 64-bit architectures). Linux uses the hash table as a cache of PTEs (essentially a level-2 TLB). TLB flushing routines (flush_tlb_page(), flush_tlb_range(),
Slide 27: PTE Management Optimization
PTE Management Optimization Basic idea: invalidate hash-table PTE when the Linux PTE is changed, rather than in the TLB flushing routines. Reverse mapping (rmap) infrastructure gives us the necessary information to do this Allows us to map from the address of a Linux PTE to virtual address and MM co
Slide 28: Optimized PTE management: results
Optimized PTE management: results 32-bit kernel (G3 PowerBook) Kernel compile: no significant change in system time or overall time for either approach. 64-bit kernel (1.45GHz POWER4+): Kernel compile: batched update vs. original implementation System time reduced from 8.51 to 8.44 seconds Total tim
Slide 29: Conclusions
Conclusions I-cache flushing and memory copy optimizations produced worthwhile performance improvements. PTE management optimization gave no significant performance improvement. Measurement is key Good ideas may not turn out to give any benefit in practice. Need both micro-benchmarks and application
Slide 30: Legal Statement
Legal Statement This work represents the view of the author and does not necessarily represent the view of IBM. IBM, PowerPC, PowerPC 750, pSeries, RS/6000, POWER3, POWER4, and POWER4+ are trademarks or registered trademarks of International Business Machines Corporation in the United States and/or