Performance Robust Parallel I O Z Morley Mao Noah Treuhaft CS258 5 17 99 Professor Culler Introduction Clusters exhibit performance heterogeneity static dynamic due to both hardware and software Consistent peak performance demands adaptive software building performance robust parallel software means keeping heterogeneity in mind This work explores adaptivity appropriate for I O bound parallel programs how to provide that adaptivity 2 Heterogeneity demands adaptivity Cluster Node Process Dis k Physical I O streams are simple to build and use But their performance is highly variable different drive models bad blocks multizone behavior file layout competing programs host bottlenecks I O bound parallel programs run at rate of slowest disk 3 Virtual Streams Performance robust programs want virtual streams that eliminate dependence on individual disk behavior continually equalize throughput delivered to processes Process Virtual Streams Layer Disk 4 Graduated Declustering GD a Virtual Streams implementation data replicated mirrored for availability use replicas to provide performance availability too fast network makes remote disk access comparable to local distributed algorithm for adaptivity client provides information about its progress server reacts by scheduling requests to even out progress client A Process GD client library server server client B GD server A B 5 GD in action Local decisions yield global behavior Before Perturbation Client0 B Client1 B Client2 B B 2 B 2 B 2 After Perturbation B 2 B 2 Client3 B B 2 Client0 7B 8 To Client0 B 2 3B 8 B 2 Client2 7B 8 B 4 B 2 B 2 From Server3 Client1 7B 8 5B 8 Client3 7B 8 To Client0 3B 8 B 4 B 2 B 2 5B 8 0 1 1 2 2 3 Server0 B Server1 B Server2 B 3 0 Server3 B From Server3 0 1 1 2 2 3 Server0 B Server1 B 2 Server2 B 3 0 Server3 B 6 Evaluation of original GD implementation progress based Seek overhead due to reading from all replicas GD Under Perturbation Percent of Peak Bandwidth Seek overhead Ideal With GD 100 90 80 70 60 50 40 30 20 10 0 Static 0 2 4 6 8 10 12 14 Disk Nodes Perturbed 7 Deficiency of original GD implementation seek overhead Under the assumption of sequential data access Seek occurs even when there is no perturbation seeks are becoming more significant as disk transfer rate increases Need a new algorithm that reads mostly from a single disk under no perturbation dynamically adjusts to perturbation when necessary achieves both performance adaptivity and minimal overhead 8 Proposed solution response ratebased GD Number of requests clients send to server based on server response rate servers use request queue lengths to make scheduling decisions uses implicit information historyless no bandwidth information transmitted between server and client advantage each client has a primary server 9 Evaluation of response rate based GD Graph of bandwidth vs disk nodes perturbed Percent of Peak Bandwidth Reduced Seek overhead GD Under Perturbation 100 90 80 70 60 50 40 30 20 10 0 Responserate based ProgressBased 0 2 4 6 8 10 12 14 Disk Nodes Perturbed 10 Historyless vs History based adaptiveness History based progress based Adjustment to perturbation occurs gradually over time Close to perfect knowledge if the information not outdated extra overhead in sending control information Historyless response rate based primary server designation possible to increase sensitivity to real perturbation by creating artificial perturbation considers varying performance of data consumers takes longer to converge 11 Stability and Convergence How long does it take for the system to converge Linear with the number of nodes Depends on the last occurrence of perturbation Influenced by the style of communication implicit vs explicit Stability of Historyless System 4 node case 1 node perturbed 4 9 4 9 4 7 4 7 Bandwidth MB sec Bandwidth MB sec Stability of Historybased System 4 node case 1 node perturbed 4 5 4 3 4 1 3 9 Node3 Avg 3 9 3 5 3 5 Time sec Node2 4 1 3 7 10 20 30 40 50 60 70 80 90 100 110 120 Node1 4 3 3 7 0 Node0 4 5 0 10 20 30 40 50 60 70 80 90 100 110 120 12 Time sec Server request handof If a server finishes all its requests it will contact other servers with the same replicas to help serve their clients workstealing server request handoff keeps all disks busy when possible design decisions How many requests to handoff Depending on the BW history of both servers depending on the size of request queue Benefit vs Cost tradeoff 13 Writes Identical to reads except Create incomplete replicas with holes track holes in metadata afterward do hole filling both for availability and for performance robustness Process 14 Conclusions What did we achieve New load balancing algorithm response rate based Deliver equal BW to parallel program processes in face of performance heterogeneity demonstrate the stability of the system reduce seek overhead server request handoff writes creates a useful abstraction for steaming I O in clusters 15 Future Work Future work hot file replication get peak BW after perturbation ceases achieve orderly replies multiple disks abstraction 16