Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Computer organization and design --- speed up things
Author Message
dukeman3

Posted: Sun Apr 03, 2016 3:01 pm   Post subject: Computer organization and design --- speed up things

Consider the following recursive mergesort algorithm (another classical divide and conquer algorithm ). Mergesort was first described by John Von Neumann in 1945. The basic idea is to divide and unsorted list x of m elements into two sublists of about half size of the original list. Repeat this operation on each sublist, and continue until we have lists of size 1 in length. Then starting with sublists of length 1, “merge” the two sublists into a single sorted list.
Mergesort( m )
var list left, right, result
if length (m ) <= 1
return m
else
var middle = length (m) / 2
for each x in m up to middle
for each x in m after middle
left = Mergesort( left )
right = Mergesort( right )
result = Merge( left, right )
return result

The merge step is carried out by the following code:

Merge( left, right )
var list result
while length ( left ) >= 0 and length ( right ) > 0
if first ( left ) <= first ( right )
append first ( left ) to result
left = rest ( left )
else
append first ( right ) to result
right = rest (right)
if length ( left ) > 0
append rest ( left ) to result
if length ( right ) > 0
append rest ( right ) to result
return result

1.Assume that you have Y cores on a multicore processor to run Mergesort. Assuming that Y is much smaller than length ( m ), express the speedup factor you might expect to obtain for values of Y and length ( m ). Plot these on a graph
2. Next, assume that Y is equal to length (m). How would this affect your conclusions your previous answer? If you were tasked without obtaining the best speedup factor possible ( i.e. Strong scaling ), explain how you might change this code to obtain it.

Dan

Posted: Tue Apr 05, 2016 12:36 am   Post subject: RE:Computer organization and design --- speed up things

No one here is going to do your homework for you. At least put some effort in to writing your own post rather then just copying and pasting your assignment.
Computer Science Canada Help with programming in C, C++, Java, PHP, Ruby, Turing, VB and more!
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 2 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: