algorithm - Guidance for DIY Implementation of Parallel Merge Sort (parallel merge) on CUDA 8 -


for past few days i've been working on scratch parallel merge sort algorithm, have been stewing on lot , while easy run sequential sort in parallel. see no reason why can't merge in parallel ground up. following link:

http://www.mcs.anl.gov/~itf/dbpp/text/node127.html

i doing parallel merge. i've been working on how recursion , loops , i'd rather recursion think have working model loop. i've scratched out work , i'll describe how want set algorithm first i'll describe merge kernel

__global__ void merge(int* data, int depth) {     sequential merge (data, left = threadidx.x, right = left + 2 ^ depth - 1); }

right left offset 2 ^ depth - 1 because that's relationship noticed in working algorithm out hand

sort 3  1  7  4  9  0  2  6  8  5        \ /   \ /   \ /   \ /   \ /      merge(left, left + 2 - 1)      1 3   4 7   0 9   2 6   5 8          \ /         \ /       /       merge(left, left + 4 - 1)      1 3 4 7     0 2 6 9    5 8             \   /          /          merge(left, left + 8 - 1)      0 1 2 3 4 6 7 9     5 8                     \  /              merge(left, size)      0 1 2 3 4 5 6 7 8 9

i thinking of doing in loop this

mergesort(int* data, int size) {     int depth = 1;      int maxdepth = log base 2 (size)      // # blocks = size / 512 threads per block     int blocks = size / 512;      // # threads = size / blocks / 2 because 1 merge per 2 elements     int threads = (size / blocks) / 2;      int index = 0;      while (depth < maxdepth)     {         merge<<< blocks / depth, threads / depth>>>(data, depth++);     } }

do seem on right track or thinking off?


Comments

Post a Comment

Popular posts from this blog

Is there a better way to structure post methods in Class Based Views -

i'm using class based views in django , never specify url in ajax calls , omit action parameter in form because know these requests go through post method of class based view. notice view - profile page make many requests depending on user updating on page - post method become convoluted , if/else mess example: def post(self, request, *args, **kwargs): # handle user changing available date if request.post.get('availabledate') != none: self.updateavailabledate(request) return jsonresponse({'result':'success'}) if request.post.get('newprojectname') != none: creative_user = creativeuserprofile.objects.get(id = request.user.id) project = project.create_project(creative_user, request.post['newprojectname']) project.save() return jsonresponse({'projectid': project.id }) if request.post.get('projectimage') != none , request.files['file']: proj...
Read more

performance - Why is XCHG reg, reg a 3 micro-op instruction on modern Intel architectures? -

i'm doing micro-optimization on performance critical part of code , came across sequence of instructions (in at&t syntax): add %rax, %rbx mov %rdx, %rax mov %rbx, %rdx i thought had use case xchg allow me shave instruction , write: add %rbx, %rax xchg %rax, %rdx however, dimay found agner fog's instruction tables , xchg 3 micro-op instruction 2 cycle latency on sandy bridge, ivy bridge, broadwell, haswell , skylake. 3 whole micro-ops , 2 cycles of latency! 3 micro-ops throws off 4-1-1-1 cadence , 2 cycle latency makes worse original in best case since last 2 instructions in original might execute in parallel. now... cpu might breaking instruction micro-ops equivalent to: mov %rax, %tmp mov %rdx, %rax mov %tmp, %rdx where tmp anonymous internal register , suppose last 2 micro-ops run in parallel latency 2 cycles. given register renaming occurs on these micro-architectures, though, doesn't make sense me done way. why wouldn't register renamer ...
Read more

c# - Asp.net web api : redirect unauthorized requst to forbidden page -

im trying redirect unauthorized request forbidden page instead i'm getting forbidden page in response body , how can fix ? here's startup class : app.createperowincontext(storecontext.create); app.createperowincontext<applicationusermanager>(applicationusermanager.create); app.createperowincontext<applicationsigninmanager>(applicationsigninmanager.create); app.usecookieauthentication(new cookieauthenticationoptions { authenticationtype = defaultauthenticationtypes.applicationcookie, expiretimespan = timespan.fromdays(30), }); app.useexternalsignincookie(defaultauthenticationtypes.externalcookie); app.usetwofactorsignincookie(defaultauthenticationtypes.twofactorcookie, timespan.fromminutes(5)); app.usetwofactorrememberbrowsercookie(defaultauthenticationtypes.twofactorrememberbrowsercookie); the method im trying reach : [httpget] [authorize(roles = "admin")] public string getcurrentusername() { return userman...
Read more