CPSC 3300 - Fall 2015
Homework 1
Due Friday, August 28
Each student must turn in a separate set of homework solutions,
but you may work together in study groups with other students
from the class. Include the names of your study group members on
the solution set you submit. (It is acceptable for the group to
prepare one document and then for each group member to turn in a
copy of that document with his or her name highlighted or circled.)
I suggest that in the interest of better participation you limit
your study group size to at most four.
Also, please provide sufficient space for your calculations and
answers so that grading will be easier.
(10 points each part)
1. Skim the following two articles. (You may use other published
sources to answer the questions; please cite those sources if
you do.)
[1.1] Piotr Luszczek, "The HPC Challenge (HPCC) Benchmark Suite,"
SC06 Conference Tutorial, Tampa, Florida, Nov. 12, 2006. [Online]
icl.cs.utk.edu/projectsfiles/hpcc/pubs/sc06_hpcc.pdf
[1.2] Fei Xinga, Haihang Youb, and Charngda Luc, "HPC Benchmark
Assessment with Statistical Analysis," Procedia Computer Science,
29, 2014, pp. 210-219. [Online] www.sciencedirect.com/science/
article/pii/S1877050914001963#
(a) Give a definition of the FFT benchmark designed for your
classmates to understand.
For example, the following definition of HPL is correct but
basically useless for most of your classmates:
The algorithm used by HPL can be summarized by the
following keywords:
- Two-dimensional block-cyclic data distribution
- Right-looking variant of the LU factorization with row
partial pivoting featuring multiple look-ahead depths
- Recursive panel factorization with pivot search and
column broadcast combined
- Various virtual panel broadcast topologies
- Bandwidth reducing swap-broadcast algorithm
- Backward substitution with look-ahead of depth 1.
[www.netlib.org/benchmark/hpl/]
The following is a better way to convey the general idea of
HPL, but it is vague.
HPL is a software package that solves a (random) dense
linear system in double precision (64 bits) arithmetic
on distributed-memory computers. It can thus be regarded
as a portable as well as freely available implementation
of the High Performance Computing Linpack Benchmark.
[www.top500.org/faq/what_hpl_benchmark]
Aim for a definition of the FFT benchmark that is in-between
the two extremes illustrated above. Aim also to describe the
computation versus communication demands of the benchmark.
(b) Which facets of a HPC system does HPL stress-test?
(c) Which facets of a HPC system does FFT stress-test?
(d) According to the tutorial, on which part of the memory
hierarchy does FFT focus?
(e) If it is true that "HPCC's Fast Fourier Transform (FFT)
kernel, rather than the High-Performance Linpack (HPL) on
which Top500 is based, is more representative of the HPC
workloads on Kraken," then why is HPL still used?
2. Skim the following three articles. (You may use other published
sources to answer the questions; please cite those sources if
you do.)
[2.1] "Exponential Growth," Wikipedia: The Free Encyclopedia,
accessed Aug. 22, 2015. [Online] en.wikipedia.org/wiki/
Exponential_growth
[2.2] Christopher Mims, "Tech World Vexed by Slow Progress on
Batteries," Wall Street Journal, Oct. 5, 2104. [Online]
www.wsj.com/articles/
tech-world-vexed-by-slow-progress-on-batteries-1412552377
[2.3] Leigh Christie, "Is it true that battery energy density
improves 5-8% per year?" Quora posting, Sept. 3, 2013. [Online]
www.quora.com/
Is-it-true-that-battery-energy-density-improves-5-8-per-year
(a) Define exponential growth.
(b) Are we seeing exponential growth in the energy density of
batteries?
(c) Based on recent trends, how long does it take on average for
the energy density of batteries to double?
(d) What are consumer electronics and appliance companies doing
in the meantime while waiting for the energy density of
batteries to significantly improve?
(e) What are computer and cell phone companies doing in the
meantime while waiting for the energy density of batteries
to significantly improve?