4-1©2006 Raj JainCSE567MWashington University in St. LouisTypes of Types of WorkloadsWorkloadsRaj Jain Washington University in Saint LouisSaint Louis, MO [email protected] slides are available on-line at:http://www.cse.wustl.edu/~jain/cse567-06/4-2©2006 Raj JainCSE567MWashington University in St. LouisOverviewOverview! Terminology! Test Workloads for Computer Systems" Addition Instruction" Instruction Mixes" Kernels" Synthetic Programs" Application Benchmarks: Sieve, Ackermann's Function, Debit-Credit, SPEC4-3©2006 Raj JainCSE567MWashington University in St. LouisPart II: Measurement Techniques and ToolsPart II: Measurement Techniques and ToolsMeasurements are not to provide numbers but insight- Ingrid Bucher1. What are the different types of workloads?2. Which workloads are commonly used by other analysts?3. How are the appropriate workload types selected?4. How is the measured workload data summarized?5. How is the system performance monitored?6. How can the desired workload be placed on the system in a controlled manner?7. How are the results of the evaluation presented?4-4©2006 Raj JainCSE567MWashington University in St. LouisTerminologyTerminology! Test workload: Any workload used in performance studies.Test workload can be real or synthetic.! Real workload: Observed on a system being used for normal operations.! Synthetic workload:" Similar to real workload" Can be applied repeatedly in a controlled manner" No large real-world data files" No sensitive data" Easily modified without affecting operation" Easily ported to different systems due to its small size" May have built-in measurement capabilities.4-5©2006 Raj JainCSE567MWashington University in St. LouisTest Workloads for Computer SystemsTest Workloads for Computer Systems1. Addition Instruction2. Instruction Mixes3. Kernels4. Synthetic Programs5. Application Benchmarks4-6©2006 Raj JainCSE567MWashington University in St. LouisAddition InstructionAddition Instruction! Processors were the most expensive and most used components of the system! Addition was the most frequent instruction4-7©2006 Raj JainCSE567MWashington University in St. LouisInstruction MixesInstruction Mixes! Instruction mix = instructions + usage frequency! Gibson mix: Developed by Jack C. Gibson in 1959 for IBM 704 systems.4-8©2006 Raj JainCSE567MWashington University in St. LouisInstruction Mixes (Cont)Instruction Mixes (Cont)! Disadvantages:" Complex classes of instructions not reflected in the mixes." Instruction time varies with:! Addressing modes! Cache hit rates! Pipeline efficiency! Interference from other devices during processor-memory access cycles! Parameter values! Frequency of zeros as a parameter! The distribution of zero digits in a multiplier! The average number of positions of preshift in floating-point add! Number of times a conditional branch is taken!4-9©2006 Raj JainCSE567MWashington University in St. LouisInstruction Mixes (Cont)Instruction Mixes (Cont)! Performance Metrics:" MIPS = Millions of Instructions Per Second" MFLOPS = Millions of Floating Point Operations Per Second4-10©2006 Raj JainCSE567MWashington University in St. LouisKernelsKernels! Kernel = nucleus! Kernel= the most frequent function! Commonly used kernels: Sieve, Puzzle, Tree Searching, Ackerman's Function, Matrix Inversion, and Sorting.! Disadvantages: Do not make use of I/O devices4-11©2006 Raj JainCSE567MWashington University in St. LouisSynthetic ProgramsSynthetic Programs! To measure I/O performance lead analysts ⇒ Exerciser loops! The first exerciser loop was by Buchholz (1969) who called it a synthetic program.! A Sample Exerciser: See program listing Figure 4.1 in the book4-12©2006 Raj JainCSE567MWashington University in St. LouisSynthetic ProgramsSynthetic Programs! Advantage:" Quickly developed and given to different vendors." No real data files" Easily modified and ported to different systems." Have built-in measurement capabilities" Measurement process is automated" Repeated easily on successive versions of the operating systems! Disadvantages:" Too small" Do not make representative memory or disk references" Mechanisms for page faults and disk cache may not be adequately exercised." CPU-I/O overlap may not be representative." Loops may create synchronizations ⇒ better or worse performance.4-13©2006 Raj JainCSE567MWashington University in St. LouisApplication BenchmarksApplication Benchmarks! For a particular industry: Debit-Credit for Banks! Benchmark = workload (Except instruction mixes)! Some Authors: Benchmark = set of programs taken from real workloads! Popular Benchmarks4-14©2006 Raj JainCSE567MWashington University in St. LouisSieveSieve! Based on Eratosthenes' sieve algorithm: find all prime numbers below a given number n.! Algorithm:" Write down all integers from 1 to n" Strike out all multiples of k, for k=2, 3, …, √n.! Example:" Write down all numbers from 1 to 20. Mark all as prime:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20! Remove all multiples of 2 from the list of primes:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 204-15©2006 Raj JainCSE567MWashington University in St. LouisSieve (Cont)Sieve (Cont)! The next integer in the sequence is 3. Remove all multiples of 3:1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20! 5 > √20 ⇒ Stop! Pascal Program to Implement the Sieve Kernel:See Program listing Figure 4.2 in the book4-16©2006 Raj JainCSE567MWashington University in St. LouisAckermann's FunctionAckermann's Function! To assess the efficiency of the procedure-calling mechanisms. The function has two parameters and is defined recursively.! Ackermann(3, n) evaluated for values of n from one to six.! Metrics:" Average execution time per call" Number of instructions executed per call, and" Stack space per call! Verification: Ackermann(3, n) = 2n+3-3! Number of recursive calls in evaluating Ackermann(3,n):(512× 4n-1-15 × 2n+3 + 9n + 37)/3Execution time per call.! Depth of the procedure calls = 2n+3-4 ⇒ stack space required doubles when n ← n+1.4-17©2006 Raj JainCSE567MWashington University in St. LouisAckermann Program in SimulaAckermann Program in Simula! See program listing Figure 4.3 in the book4-18©2006 Raj JainCSE567MWashington University in St. LouisOther BenchmarksOther Benchmarks! Whetstone! U.S. Steel! LINPACK! Dhrystone! Doduc! TOP! Lawrence Livermore Loops! Digital Review Labs! Abingdon Cross Image-Processing
View Full Document
Unlocking...