Browsing by Subject "Branch"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item CPU performance in the age of big data : a case study with Hive(2016-12) Shulyak, Alexander Cole; John, Lizy KurianDistributed SQL Query Engines (DSQEs), like Hive, Shark, and Impala, have become the de-facto database set-up for Decision Support Systems with large database sizes. Unlike their single-threaded counterparts like MySQL, DSQEs experience inefficiencies related to the algorithm, code base, OS, and CPU micro-architecture that limit throughput despite the speedup from distributed execution. In my thesis, I present a detailed performance analysis of a DSQE called Hive, comparing it to MySQL, a single-threaded database application. Hive has difficulty converting queries into a set of MapReduce jobs for distributed execution. Hive also experiences a startup phase that is a significant overhead for short running queries. Additionally, both Hive and MySQL, like other server applications, experience high L1I miss rates due to a large code footprint. However, because MySQL is algorithmically efficient and traverses the database at a faster rate, it incurs a larger back-end bottleneck from LLC misses, which hides the front-end bottleneck. In contrast, Hive does not hide the high L1I cache miss rate with back-end stalls. Additionally, the higher context switch rates experienced by multi-process Hive setups thrash the first level caches, further inflaming the L1I cache miss rate. To address this micro-architectural inefficiency, I propose an instruction prefetch mechanism called Runahead Prefetch. It is similar to previously proposed branch prediction base prefetchers [19], but designed to easily extend modern Intel microarchitectures. Despite newer instruction prefetch mechanisms that discount branch prediction based prefching potential [8] [9] [12], I show Runahead Prefetch can eliminate 92% of L1I misses and 96% of icache stalls on average given modern branch misprediction rates and sufficient runahead.Item The classifiction of M-curves of bidegree (d,3) in the torus(2005-05) Williams, Lina Mabel; Korchagin, Anatoly; Weinberg, David A.; Wang, AlexThe classification, up to homeomorphism, of real algebraic curves in the projective plane was the first part of Hilbert's sixteenth problem. We provide a classification for a new family of curves in the torus. More precisely, a real homogeneous polynomial f(u,v,x,y) is said to be of bidegree (d,e) if it is homogeneous of degree d (resp. e) with respect to the variables (u,v) (resp. (x,y)). Such polynomials then have naturally defined zero sets on the torus T, provided one realizes T as the product of two real projective lines. The real zero set of f in T is then said to be an M-curve of bidegree (d,e) if it has maximally many real connected components. We completely classify all M-curves of bidegree (d,3) on the torus. In particular, we show that for any integer d (with d>=2), there are M-curves of bidegree (d,3) realizing the class 2(d-1) O + in H_1(T), where O is homologous to 0, a and b are the generators of H_1(T), and n<=d is any integer with the same parity as d.Item The classifiction of m-curves of bidegree (d,3) on Torus(Texas Tech University, 2005-05) Williams, Lina Mabel; Korchagin, Anatoly; Weinberg, David A.; Wang, XiaochangThe classification, up to homeomorphism, of real algebraic curves in the projective plane was the first part of Hilbert's sixteenth problem. We provide a classification for a new family of curves in the torus. More precisely, a real homogeneous polynomial f(u,v,x,y) is said to be of bidegree (d,e) if it is homogeneous of degree d (resp. e) with respect to the variables (u,v) (resp. (x,y)). Such polynomials then have naturally defined zero sets on the torus T, provided one realizes T as the product of two real projective lines. The real zero set of f in T is then said to be an M-curve of bidegree (d,e) if it has maximally many real connected components. We completely classify all M-curves of bidegree (d,3) on the torus. In particular, we show that for any integer d (with d>=2), there are M-curves of bidegree (d,3) realizing the class 2(d-1) O + in H_1(T), where O is homologous to 0, a and b are the generators of H_1(T), and n<=d is any integer with the same parity as d.