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

Write an algorithm inputs speed of cars using pseudocode, Write an algorith...

Write an algorithm by using pseudocode which: Inputs top speeds of 5000 cars Outputs fastest speed and the slowest speed Outputs average speed of all the 5000 cars

What is bubble sort, What is bubble sort? Bubble Sort: The basic ide...

What is bubble sort? Bubble Sort: The basic idea in bubble sort is to scan the array to be sorted sequentially various times. Every pass puts the largest element in its corr

Algorithm.., write an algorithm to sort given numbers in ascending order us...

write an algorithm to sort given numbers in ascending order using bubble sort

Implementation of multiple queues, Thus far, we have seen the demonstration...

Thus far, we have seen the demonstration of a single queue, but several practical applications in computer science needs several queues. Multi queue is data structure in which mult

Calculate address of an element in an array., Q. Explain the technique to c...

Q. Explain the technique to calculate the address of an element in an array. A  25 × 4  matrix array DATA is stored in memory in 'row-major order'. If base  address is 200 and

Random searching, write aprogram for random -search to implement if a[i]=x;...

write aprogram for random -search to implement if a[i]=x;then terminate other wise continue the search by picking new randon inex into a

Algorithm, Ask question #MWhich of the following is not a characteristic of...

Ask question #MWhich of the following is not a characteristic of good algorithm? inimum 100 words accepted#

Insertion of a key into a b-tree, Example: Insertion of a key 33 into a B-...

Example: Insertion of a key 33 into a B-Tree (w/split) Step 1: Search first node for key closet to 33. Key 30 was determined. Step 2: Node pointed through key 30, is se

Insert function, INSERT FUNCTION /*prototypes of insert & find function...

INSERT FUNCTION /*prototypes of insert & find functions */ list * insert_list(list *); list * find(list *, int); /*definition of  anyinsert function */ list * inser

System defined data types, System defined data types:- These are data t...

System defined data types:- These are data types that have been defined by the compiler of any program. The C language contains 4 basic data types:- Int, float,  char and doubl

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