Divide and Conquer 基本思想 Divide-and-conquer: Break up problem into several parts. Solve each part recursively. Combine solutions to sub-problems into overall solution. Most common usage. Break up problem of size n into two equal parts of size ½ n.……
Greedy Algorithm Interval Scheduling Job j starts at $s_j$ and finishes at $f_j$. Two jobs compatible if they don't overlap. Goal: find maximum subset of mutually compatible jobs. Greedy algorithm. Consider jobs in increasing order of finish time.Take each job provided it's……
Graph Basic Definitions and Applications Undirected Graphs Undirected graph. G = (V, E) V = nodes. E = edges between pairs of nodes. Captures pairwise relationship between objects. Graph size parameters: n = |V|, m = |E|. Directed Graphs Graph Representation Adjacency……
Stable Matching Definition Goal: Given n men and n women, find a "suitable" matching. Participants rate members of opposite sex. Each man lists women in order of preference from best to worst. Each woman lists men in order of preference from best……
Introduction Goal: replacing large inefficient processors with many smaller, efficient processors to get better performance per joule Multiprocessors, cluster Scalability, availability, power efficiency Task-level (process-level) parallelism High throughput for independent jobs Parallel processing program Single program run on multiple processors Multicore microprocessors Chips with multiple processors (cores) Shared Memory Processors (SMP) Hardware and Software Challenge: hardware and software design that enables parallel processing programs, which can be efficiently executed (in performance and energy) when number of cores scales.
Virtual Memory Dependable memory hierarchy Dependability Dependability Measures: Reliability: mean time to failure (MTTF) Service interruption: mean time to repair (MTTR) Mean time between failures MTBF = MTTF + MTTR Availability = MTTF / (MTTF + MTTR) Improving Availability Increase MTTF: fault……
Measuring Cache Performance Components of CPU time Program execution cycles 【execution】 Includes cache hit time Memory stall cycles 【IO】 Mainly from cache misses With simplifying assumptions: $,,,,,,,Memory,stall,cycles\ = \frac{memory,access}{Program}\times……
Cache Hierarchies Data and instructions are stored on DRAM chips DRAM is a technology that has high bit density, but relatively poor latency an access to data in memory can take as many as 300 cycles! Hence, some data is stored on……