Computer Science Canada

Computer organization and design --- speed up things

Author:  dukeman3 [ 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 
      var middle = length (m) / 2 
      for each x in m up to middle 
         add x to left 
      for each x in m after middle 
         add x to right 
         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 ) 
                    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.

Author:  Dan [ 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.