//This micro-kernel currently does not use shared memory
//It could be improved by adding this caching.

//This micro-kernel currently uses a selection sort.
//This is done for simplicity of testing and should be replaced
//  before using it for serious testing with a better sort.

__device__ void Sort( void* param)
{
    float* paramIn = (float*)param;
    int N = (int)(*paramIn);
    float* a  = paramIn+1;  //input data, will currently be trashed
    float* b  = a + N*sizeof(float); //location for result array

    int warp_size = 32;
    int tid = threadIdx.x%warp_size;

    float *sub = a + tid*N/warp_size;  //Sub list that each warp will sort
    
    //Selection Sort, eventually do Merge or something faster
    int i, j;
    for(i=0; i<N/warp_size-1; i++){
      //Find min is remaining list
      int min = i;
      for(j=i+1; j<N/warp_size; j++){
        if(sub[j]<sub[min])min = j;
      }
      //Swap ith place with min
      float temp = sub[i];
      sub[i]=sub[min];
      sub[min]=temp;
    }

    //Merge loops
    int subs;  //number of sub lists I currently have
    for(subs=warp_size; subs!=1; subs=subs/2){
      if(tid<subs/2){
        //Merge our two lists
        int sub_size = N/subs;
        float *sub1 = a + 2*tid*sub_size;
        float *sub2 = sub1 + sub_size;
        
        float *ret = b + 2*tid*sub_size;
        
        //Merge our two lists into their location in ret
        int p1 = 0;  //place in first list
        int p2 = 0;  //place in second list
        int cur= 0;
        while(p1<sub_size && p2<sub_size){
          if(sub1[p1]<sub[p2]){
            ret[cur++] = sub1[p1++];
          }else{
            ret[cur++] = sub2[p2++];
          }
        }
        //Copy any elements left in our lists after the first list runs out
        while(p1<sub_size) ret[cur++]=sub1[p1++];
        while(p2<sub_size) ret[cur++]=sub2[p2++];

        int k;
        for(k=0;k<2*sub_size;k++)sub1[k]=ret[k];
      }
      /*      //Copy the now sorted sub arrays back into sub to be merged again
      int k;
      for(k=tid; k<N; k+=warp_size) a[k]=b[k];
      */
    }
}

	.file	"tmpxft_0033bd78_00000000-6_Sort.cudafe1.cpp"
	.text
#APP

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB2011:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE2011:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.globl	_Z4SortPv
	.type	_Z4SortPv, @function
_Z4SortPv:
.LFB2008:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	popq	%rax
	.cfi_def_cfa_offset 8
	subq	$24, %rsp
	.cfi_def_cfa_offset 32
	movl	$1, 12(%rsp)
	movl	12(%rsp), %edi
	call	exit@PLT
	.cfi_endproc
.LFE2008:
	.size	_Z4SortPv, .-_Z4SortPv
	.section	.text.startup,"ax",@progbits
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB2034:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	movq	%rax, %rdi
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rdx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE2034:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:


#include <hip/hip_runtime.h>
//This micro-kernel currently does not use shared memory
//It could be improved by adding this caching.

//This micro-kernel currently uses a selection sort.
//This is done for simplicity of testing and should be replaced
//  before using it for serious testing with a better sort.

__device__ void Sort( void* param)
{
    float* paramIn = (float*)param;
    int N = (int)(*paramIn);
    float* a  = paramIn+1;  //input data, will currently be trashed
    float* b  = a + N*sizeof(float); //location for result array

    int warp_size = 32;
    int tid = threadIdx.x%warp_size;

    float *sub = a + tid*N/warp_size;  //Sub list that each warp will sort
    
    //Selection Sort, eventually do Merge or something faster
    int i, j;
    for(i=0; i<N/warp_size-1; i++){
      //Find min is remaining list
      int min = i;
      for(j=i+1; j<N/warp_size; j++){
        if(sub[j]<sub[min])min = j;
      }
      //Swap ith place with min
      float temp = sub[i];
      sub[i]=sub[min];
      sub[min]=temp;
    }

    //Merge loops
    int subs;  //number of sub lists I currently have
    for(subs=warp_size; subs!=1; subs=subs/2){
      if(tid<subs/2){
        //Merge our two lists
        int sub_size = N/subs;
        float *sub1 = a + 2*tid*sub_size;
        float *sub2 = sub1 + sub_size;
        
        float *ret = b + 2*tid*sub_size;
        
        //Merge our two lists into their location in ret
        int p1 = 0;  //place in first list
        int p2 = 0;  //place in second list
        int cur= 0;
        while(p1<sub_size && p2<sub_size){
          if(sub1[p1]<sub[p2]){
            ret[cur++] = sub1[p1++];
          }else{
            ret[cur++] = sub2[p2++];
          }
        }
        //Copy any elements left in our lists after the first list runs out
        while(p1<sub_size) ret[cur++]=sub1[p1++];
        while(p2<sub_size) ret[cur++]=sub2[p2++];

        int k;
        for(k=0;k<2*sub_size;k++)sub1[k]=ret[k];
      }
      /*      //Copy the now sorted sub arrays back into sub to be merged again
      int k;
      for(k=tid; k<N; k+=warp_size) a[k]=b[k];
      */
    }
}

	.text
	.file	"Sort.hip"
	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_

	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.amdgpu_metadata
---
amdhsa.kernels:  []
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
