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

Data structures, 1.  You are required to hand in both a hard copy and an el...

1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You

Sequential files, Data records are stored in some particular sequence e.g.,...

Data records are stored in some particular sequence e.g., order of arrival value of key field etc. Records of sequential file cannot be randomly accessed i.e., to access the n th

Implementation of stack, In this unit, we have learned how the stacks are i...

In this unit, we have learned how the stacks are implemented using arrays and using liked list. Also, the advantages and disadvantages of using these two schemes were discussed. Fo

Analyze an algorithm, In order to analyze an algorithm is to find out the a...

In order to analyze an algorithm is to find out the amount of resources (like time & storage) that are utilized to execute. Mostly algorithms are designed to work along with inputs

Process of decision making under uncertainty, (a) Describe the steps involv...

(a) Describe the steps involved in the process of decision making under uncertainty. (b) Explain the following principles of decision making: (i) Laplace, (ii) Hurwicz. (c

Explain the concept of hidden lines and surface removal, Explain the concep...

Explain the concept of hidden lines The problem of hidden lines or surfaces was implicit even in 2-D graphics, but we did not mention it there, because what was intended to be

Example which cause problems for hidden-surface algorithms, Example which c...

Example which cause problems for some hidden-surface algorithms Some special cases, which cause problems for some hidden-surface algorithms, are penetrating faces and cyclic ov

Acyclic graph, Tree is a widely used data structure employed for representi...

Tree is a widely used data structure employed for representing several problems. We studied tree like a special case of acyclic graph. Though, rooted trees are most prominent of al

Data type, Data type An implementation of an abstract data type on a...

Data type An implementation of an abstract data type on a computer. Therefore, for instance, Boolean ADT is implemented as the Boolean type in Java, and bool type in C++;

Function performs multiplication of two numbers, You need to write a functi...

You need to write a function that performs multiplication of two numbers in your data structure. Again, remember how you multiply numbers in base 10 and you should be fine. Multipl

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