Need a C code, Please help. The following is a high-level pseudocode description

Question

Need a C code, Please help.

The following is a high-level pseudocode description of the algorithm: Algorithm 1 Shell sort like parallel algorithm (Phase I: Hypercube Compare Exchange. 2: for i (d 1) to 0 do 3: if (i-th bit of rank) 1 then 4: compare-split-hi(i 5: else compare-split-low(i); 7: Phase II: Odd-even Transposition Iterations. 8: done FALSE 9: while done FALSE do 10 11 12 broadcast FALSE to all processes; 13: else 14: broadcast TRUE to all processes; 15 if all processes broadcast TRUE then done TRUE 16

Explanation / Answer

#include <stdio.h>

void InsertionParallelSort(int size, int *arr)
{
int i, j, vv;
for (i = 1; i < size; i++) {
vv = arr[i];
j = i;
while (arr[j-1] > vv) {
arr[j] = arr[j-1];
j--;
if (j <= 0) break;
}
arr[j] = vv;
}
}

void ParallelShellsort(int size, int *arr)
{
int i, j, hh, vv;
hh = 1; while (hh < size) hh = 3*hh + 1;
hh /= 3;
while (hh != 1) {
hh /= 3;
for (i = hh; i < size; i++) {
vv = arr[i]; j = i;
while (arr[j-hh] > vv) {
arr[j] = arr[j-hh];
j = j-hh;
if (j <= hh) break;
}
arr[j] = vv;
}
hh /= 3;
}
InsertionParallelSort(size,arr); // cleaning up the code
for(i=0;i<size;i++){
   printf("%d",arr[i]);
}
}

int main(){
   int arr[10] = {2,3,5,4,6,7,8,1,10,9};
   ParallelShellsort(10,arr);
   return 0;
}

EQUIVALENT MPI CODE

InsertionParallelSort(int, int*):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-20], edi
mov QWORD PTR [rbp-32], rsi
mov DWORD PTR [rbp-4], 1
.L6:
mov eax, DWORD PTR [rbp-4]
cmp eax, DWORD PTR [rbp-20]
jge .L7
mov eax, DWORD PTR [rbp-4]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rax, rdx
mov eax, DWORD PTR [rax]
mov DWORD PTR [rbp-12], eax
mov eax, DWORD PTR [rbp-4]
mov DWORD PTR [rbp-8], eax
.L5:
mov eax, DWORD PTR [rbp-8]
cdqe
sal rax, 2
lea rdx, [rax-4]
mov rax, QWORD PTR [rbp-32]
add rax, rdx
mov eax, DWORD PTR [rax]
cmp eax, DWORD PTR [rbp-12]
jle .L3
mov eax, DWORD PTR [rbp-8]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rdx, rax
mov eax, DWORD PTR [rbp-8]
cdqe
sal rax, 2
lea rcx, [rax-4]
mov rax, QWORD PTR [rbp-32]
add rax, rcx
mov eax, DWORD PTR [rax]
mov DWORD PTR [rdx], eax
sub DWORD PTR [rbp-8], 1
cmp DWORD PTR [rbp-8], 0
jle .L8
jmp .L5
.L8:
nop
.L3:
mov eax, DWORD PTR [rbp-8]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rdx, rax
mov eax, DWORD PTR [rbp-12]
mov DWORD PTR [rdx], eax
add DWORD PTR [rbp-4], 1
jmp .L6
.L7:
nop
pop rbp
ret
.LC0:
.string "%d"
ParallelShellsort(int, int*):
push rbp
mov rbp, rsp
sub rsp, 32
mov DWORD PTR [rbp-20], edi
mov QWORD PTR [rbp-32], rsi
mov DWORD PTR [rbp-12], 1
.L11:
mov eax, DWORD PTR [rbp-12]
cmp eax, DWORD PTR [rbp-20]
jge .L10
mov edx, DWORD PTR [rbp-12]
mov eax, edx
add eax, eax
add eax, edx
add eax, 1
mov DWORD PTR [rbp-12], eax
jmp .L11
.L10:
mov ecx, DWORD PTR [rbp-12]
mov edx, 1431655766
mov eax, ecx
imul edx
mov eax, ecx
sar eax, 31
sub edx, eax
mov eax, edx
mov DWORD PTR [rbp-12], eax
.L18:
cmp DWORD PTR [rbp-12], 1
je .L12
mov ecx, DWORD PTR [rbp-12]
mov edx, 1431655766
mov eax, ecx
imul edx
mov eax, ecx
sar eax, 31
sub edx, eax
mov eax, edx
mov DWORD PTR [rbp-12], eax
mov eax, DWORD PTR [rbp-12]
mov DWORD PTR [rbp-4], eax
.L17:
mov eax, DWORD PTR [rbp-4]
cmp eax, DWORD PTR [rbp-20]
jge .L13
mov eax, DWORD PTR [rbp-4]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rax, rdx
mov eax, DWORD PTR [rax]
mov DWORD PTR [rbp-16], eax
mov eax, DWORD PTR [rbp-4]
mov DWORD PTR [rbp-8], eax
.L16:
mov eax, DWORD PTR [rbp-8]
sub eax, DWORD PTR [rbp-12]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rax, rdx
mov eax, DWORD PTR [rax]
cmp eax, DWORD PTR [rbp-16]
jle .L14
mov eax, DWORD PTR [rbp-8]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rdx, rax
mov eax, DWORD PTR [rbp-8]
sub eax, DWORD PTR [rbp-12]
cdqe
lea rcx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rax, rcx
mov eax, DWORD PTR [rax]
mov DWORD PTR [rdx], eax
mov eax, DWORD PTR [rbp-12]
sub DWORD PTR [rbp-8], eax
mov eax, DWORD PTR [rbp-8]
cmp eax, DWORD PTR [rbp-12]
jle .L21
jmp .L16
.L21:
nop
.L14:
mov eax, DWORD PTR [rbp-8]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rdx, rax
mov eax, DWORD PTR [rbp-16]
mov DWORD PTR [rdx], eax
add DWORD PTR [rbp-4], 1
jmp .L17
.L13:
mov ecx, DWORD PTR [rbp-12]
mov edx, 1431655766
mov eax, ecx
imul edx
mov eax, ecx
sar eax, 31
sub edx, eax
mov eax, edx
mov DWORD PTR [rbp-12], eax
jmp .L18
.L12:
mov rdx, QWORD PTR [rbp-32]
mov eax, DWORD PTR [rbp-20]
mov rsi, rdx
mov edi, eax
call InsertionParallelSort(int, int*)
mov DWORD PTR [rbp-4], 0
.L20:
mov eax, DWORD PTR [rbp-4]
cmp eax, DWORD PTR [rbp-20]
jge .L22
mov eax, DWORD PTR [rbp-4]
cdqe
lea rdx, [0+rax*4]
mov rax, QWORD PTR [rbp-32]
add rax, rdx
mov eax, DWORD PTR [rax]
mov esi, eax
mov edi, OFFSET FLAT:.LC0
mov eax, 0
call printf
add DWORD PTR [rbp-4], 1
jmp .L20
.L22:
nop
leave
ret
main:
push rbp
mov rbp, rsp
sub rsp, 48
mov DWORD PTR [rbp-48], 2
mov DWORD PTR [rbp-44], 3
mov DWORD PTR [rbp-40], 5
mov DWORD PTR [rbp-36], 4
mov DWORD PTR [rbp-32], 6
mov DWORD PTR [rbp-28], 7
mov DWORD PTR [rbp-24], 8
mov DWORD PTR [rbp-20], 1
mov DWORD PTR [rbp-16], 10
mov DWORD PTR [rbp-12], 9
lea rax, [rbp-48]
mov rsi, rax
mov edi, 10
call ParallelShellsort(int, int*)
mov eax, 0
leave
ret

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.