User Account

All Pages

hw7, Data Structure & Algorithms

Assignment Help:
Handout 15
COMP 264: Introduction to Computer Systems (Section 001)
Spring 2013
R. I. Greenberg
Computer Science Department
Loyola University
Water TowerCampus, Lewis Towers 524
820 N. Michigan Ave.
Chicago, Illinois 60611-2147
Assignment #7
Issued 4/12
Due (at class time) 4/22
Best to hand in all solutions through the online submission mechansim of the course web
page. No fancy diagramming is required; you can scan something hand-drawn, or use any
simple online tool of your choosing. Just make sure you end up with a common format
that will be easy to handle, for example .pdf, .jpg, .txt or even .doc or .docx if you must.
Also make sure that your submission name is appropriate to the le type, e.g., 7.pdf or
7.txt, etc. (You also can submit directly on shannon/knuth if you are working there by
copying your le to the directory ~rig/c264hw7sub with lename in the form Email-X.EXT,
where Email is your email address, X is a string of eight or more \random" alphanumeric
characters, and EXT is the le type (i.e. do a command similar to, the following with the
correct replacements for EXT, YOUREMAILADDRESS, and RANDOM:
cp 7.EXT ~rig/c264hw7sub/YOUREMAILADDRESS-RANDOM.EXT
)
HW7-1 (43 points) Suppose we wish to write a procedure that computes the inner
product of two vectors u and v. An abstract version of the function has a CPE of 16{17
with x86-64 and 26{29 with IA32 for integer, single-precision, and double-precision data. By
doing the same sort of transformations we did to transform the abstract program combine1
into the more ecient combine4, we get the following code:
void inner4(vec_ptr u, vec_ptr v, data t *dest) {
long int i;
int length = vec_length(u);
data_t *udata = get_vec_start(u);
data_t *vdata = get_vec_start(v);
data_t sum = (data_t) 0;
for (i = 0; i < length; i++){
sum = sum + udata[i] * vdata[i];
}
*dest = sum;
}
Our measurements show that this function has a CPE of 3.00 for integer and
oating-
point data. For data type float, the x86-64 assembly code for the inner loop is as follows
(udata in %rbx, vdata in %rax, limit in %rcx, i in %rdx, sum in %xmm1):
.L87: ; loop:
movss (%rbx,%rdx,4), %xmm0 ; Get udata[i]
mulss (%rax,%rdx,4), %xmm0 ; Multiply by vdata[i]
addss (%xmm0, %xmm1 ; Add to sum
addq $1, %rdx ; Increment i
cmpq %rcx, %rdx ; Compare i:limit
jl .L87 ; If <, goto loop
Assume that the functional units have the latencies and issue times given in Figure 5.12
(and in the course notes).
A. Diagram how this instruction sequence would be decoded into operations, and show how
the data dependencies between them would create a critical path of operations in the style
of Figures 5.13 (fpb-sequential.ppt) and 5.14 (fpb-
ow.ppt and fpb-
ow-abstract.ppt). (25
points.)
B. For data type float, what lower bound on the CPE is determined by the critical path?
(6 points.)
C. Assuming similar instruction sequences for the integer code as well, what lower bound on
the CPE is determined by the critical path for integer data? (6 points.)
D. Explain how the two
oating-point versions can have CPEs of 3.00 even though the
multiplication operation requires either 4 or 5 cycles. (6 points.)
HW7-2 (27 points) Write a version of the inner product procedure described in the
previous problem that uses four-way loop unrolling. (11 points.)
For x86-64, our measurements of the unrolled version give a CPE of 2.00 for integer data
but still 3.00 for both single and double precision
oating point.
A. Explain why any version of any inner product procedure cannot achieve a CPE less than
2.00. (8 points.)
B. Explain why the performance for
oating-point data did not improve with loop unrolling.
(8 points.)

Related Discussions:- hw7

Representation of a polynomial with a singly linked list, List areutilized ...

List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Implementation of dequeue, Dequeue (a double ended queue) is an abstract da...

Dequeue (a double ended queue) is an abstract data type alike to queue, where insertion and deletion of elements are allowed at both of the ends. Like a linear queue & a circular q

Graph search using iterative deepening, Prove that uniform cost search and ...

Prove that uniform cost search and breadth- first search with constant steps are optimal when used with the Graph-Search algorithm (see Figure). Show a state space with varying ste

Balance theorem, Question 1 Discuss the following theorems with respect to...

Question 1 Discuss the following theorems with respect to Splay Trees- Balance Theorem Dynamic Finger Theorem   Question 2 Write a C program for implementation

Help with Assignment, Need help with Data Structures assignment requiring C...

Need help with Data Structures assignment requiring C++ program

Determine the stereo vision, Determine the stereo vision There is still...

Determine the stereo vision There is still one more major item missing, before we can look at a computer display or plot and perceive it just as we see a real object, namely th

Pseudo code, since the gregorian calendar was introduced in 1752,a leap yea...

since the gregorian calendar was introduced in 1752,a leap year occurs every 4 years.you are to write a pseudo code to find out whether a year is a leap year.your progrm should dis

Procedure to delete all terminal nodes of the tree, Q. Let a binary tree 'T...

Q. Let a binary tree 'T' be in memory. Write a procedure to delete all terminal nodes of the tree.       A n s . fun ction to Delete Terminal Nodes from Binary Tree

General Tree, How to create an General Tree and how to search general tree?...

How to create an General Tree and how to search general tree?

Determine the class invariants- ruby, Determine the class invariants- Ruby ...

Determine the class invariants- Ruby Ruby has many predefined exceptions classes (like ArgumentError) and new ones can be created easily by sub-classing StandardError, so it's

Write Your Message!

Captcha
Order Assignment

Featured Services

Order Now

Popular Subjects

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

Submit Assignment

Academics

Major Subjects

Majors

Get In Touch

whatsapp: +91-977-207-8620

Phone: +91-977-207-8620

Email: [email protected]

TERMS & POLICIES

HELP & SUPPORT

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd