A problem in Multithreading Sort
hi
I'm learning Multithreading programming.A problem come into my face.
I programmed a quicksort-program(use multithreading) to sort some numbers in a file.
the brief thread-function as follows:
DWORD WINAPI ThreadFunc(LPVOID lpParameter) //sort p[a] to p[b],total number n=b-a
{
...
if(n<1000||ThreadNum>20) //total number<1000 or total thread>20
{
//Call quick sort func
}
else
{
long privot=partition(p,a,b); //divide p[a-b] into 2 part，and then sort each part
CreateThread(..,ThreadFunc,...);//sort p[a] to p[privot-1]
ThreadNum++;
CreateThread(...,ThreadFunc,...);//sort p[privot+1] to p[b]
ThreadNum++;
}
...
}
as you see ThreadNum is not a const.
so,how can i know the whole sort is finished??
thanks
# 1 Re: A problem in Multithreading Sort
Didn't see where you're merging your "sort"s!
Why are you creating from each thread another 2 threads, when you know from the beginning how many threads you need? For example, when you have 4324 numbers to sort, you could create 4 threads (sorting 1000 numbers each) besides the main thread that will sort the remaining 324 numbers, and then wait for the other threads to finish their sort. Before exiting the main thread, merge the 5 segments of sorted numbers.
In fact, your "tutor" needs to be told that it is pointless to sort multithreaded on single processor machines, thus, would be probably sufficient to split the sort in ONLY 2 parts, since most computers have maximum 2 processors (dual processor). I wouldn't bother creating more than 2 threads for such purpose, which btw proves better the understanding of multithreading.
The best thing to know in multithreaded programming is the optimal number of threads needed to solve the problem. You've discovered that... the rest is easy.
Regards,
# 2 Re: A problem in Multithreading Sort
hi,Bornish
Thanks for the reply.
I am sorry.I haven't expressed my func clearly.
my program don't need merge.
I use MapViewOfFile() to get the pointer p.
the partition() divide p[a-b] into 2 part (eg: part A&part B)
p[a]~p[privot-1]<p[privot]<p[privot+1]~p[b]
part A < key < part B
then i only need to sort partA ,partB
unsigned long partiton(unsigned long *p,long low,long high)//divide p[low-high] into 2 parts
{
unsigned long key=p[low];//the key to reference
while(low<high)
{
while(low<high&&key<p[high])
high--;
swap(&p[high],&p[low]);
while(low<high&&key>p[low])
low++;
swap(&p[high],&p[low]);
} //now p[i](i<low)<key,p[j](j>low)>key
return low;
}
the partiton() works well.
btw i just want to let the program more flexible
so i assume i don't know how many numbers in the target file.
thanks again.
# 3 Re: A problem in Multithreading Sort
Maybe merge wasn't the best word to use. I'll explain what I meant.
Take for example:
"8,4,6,0,2,5,9,7,1,3" as input. If each thread takes half as input to sort:
- T1 takes "8,4,6,0,2" and results "0,2,4,6,8"
- T2 takes "5,9,7,1,3" and results "1,3,5,7,9"
If you don't <merge> these sorted halfs into a properly sorted array, you'll get:
"0,2,4,6,8,1,3,5,7,9" instead of "1,2,3,4,5,6,7,8,9,0" which would be correct.
For second issue, I would still recommend running a fixed number of threads (more precisely two), no matter the target's size. Even with dynamic target size you could implement the following (in pseudocode):void * result; // final result
void * data; // current chunk of data
void * sorted; // current sorted chunk of data
DWORD slaveID; // slave thread ID
/*!
Slave thread sorting a chunk / partition of the target data.*/
void slave() {
while (data) {
SortData(data);
Suspend(slaveID);
}
}
/*!
Master thread responsible of:
- reading / saving data
- starting / resuming slave thread whenever required
- zipping current chunk within final result.*/
void master() {
data = ReadFirstChunk();
slaveID = CreateThread(slave);
do {
WaitSuspendedState(slaveID);
sorted = data;
data = ReadNextChunk();
Resume(slaveID);
result = MergeByZipping(result,sorted);
} until (data);
Save(result);
}Regards,
# 4 Re: A problem in Multithreading Sort
hi,Bornish
I've tried your code .It works well!
However,I wonder if my concept is correct.(I still think my algorithm is better,if i solved the sort-finish problem)
Maybe I've confused you again,sorry.
my algorithm eg:
"5,4,6,0,2,8,9,7,1,3" as input.
i use the first element "5" as the key.
after the partiton() call,the array result "3,4,1,0,2,5,7,9,8,6"
we just need sort "3,4,1,0,2" and "7,9,8,6".without merge
In this way,I think it can show the advantage of multithreading in sort.
thanks again
# 5 Re: A problem in Multithreading Sort
Ah, now I understand how your partition works.
Didn't see any sorting in your thread function... thus I didn't understand why you were starting 2 new threads, instead of only one. Simplest way you could signal when all threads have finished without waiting for each other (not required) would be a counter that increases every time you start a thread, and decreases when a thread ends.
This would be the pseudocode:DWORD thCount;
void threadFn(a,b) {
mid = Sort(a,b); // returns position of the moved key element
if (a+1<mid) {
++thCount;
CreateThread(threadFn,a,mid);
}
if (mid<b-1) {
++thCount;
CreateThread(threadFn,a,mid);
}
--thCount;
}
void main() {
thCount = 1;
CreateThread(threadFn);
while (thCount) {
PeekAndPumpMsgs(); // any piece of code known to peek and pump messages
}
}Regards,
# 6 Re: A problem in Multithreading Sort
hi
It seems the problem is more complicated than i thought...
the result is not correct!
the sub-thread func seems do nothing.
all the code pasted:
DWORD WINAPI sort(LPVOID ptr);
int threadnum=0;
unsigned long *pmem=NULL;
int tflag=0;
void CThreadSortDlg::OnOK()
{
// TODO: Add extra validation here
unsigned long size,n;
HANDLE hfile;
HANDLE hmap;
HANDLE hthread=NULL;
static char BASED_CODE szFilter[]="Data Files|*.dat;*.DAT||";
CFileDialog filebox(TRUE,".dat","output",OFN_HIDEREADONLY|OFN_OVERWRITEPROMPT,szFilter);
filebox.m_ofn.lpstrTitle="Open";
if(filebox.DoModal()==IDOK)
{
//////////////////////////////////////Getpath
CString path=filebox.GetPathName();
hfile=CreateFile(path,GENERIC_READ|GENERIC_WRITE,FILE_SHARE_READ|FILE_SHARE_WRITE,NULL,OPEN_EXISTING,FILE_ATTRIBUTE_ARCHIVE,NULL);
if(hfile==0)
{
GetDlgItem(IDC_EDIT)->SetWindowText("File not exist!");
return;
}
//////////////////////////////////////FileMap
if((hmap=CreateFileMapping(hfile,NULL,PAGE_READWRITE,0,0,NULL))==NULL)
{
GetDlgItem(IDC_EDIT)->SetWindowText("File Map fail!");
CloseHandle(hfile);
return;
}
pmem=(unsigned long *)MapViewOfFile(hmap,FILE_MAP_ALL_ACCESS,0,0,0);
n=GetFileSize(hfile,NULL);
////////////////////////////////////////create thread
DWORD threadid;
unsigned long *param=new DWORD [2];
param[0]=0;
param[1]=n/4-1; //number type:unsigned long
HANDLE hthread=CreateThread(NULL,NULL,&sort,param,0,&threadid);
if(hthread==NULL)
{
MessageBox(NULL,"thread create error","note",MB_OK);
return 1;
}
threadnum++;
tflag++;
CloseHandle(hthread);
/////////////////////////////////////////////////
while(tflag==0); //wait the sort finish
//Sleep(5000);
WriteFile(hfile,(unsigned long *)pmem,n,&size,NULL);
UnmapViewOfFile((void *)pmem);
char buff[10];
memset(buff,0,10);
sprintf(buff,"Thread Number: %d",threadnum);
GetDlgItem(IDC_EDIT)->SetWindowText(buff);
CloseHandle(hfile);
CloseHandle(hmap);
}
//CDialog::OnOK();
}
void xchg(unsigned long *a,unsigned long *b) //exchange data
{
unsigned long tmp=*a;
*a=*b;
*b=tmp;
}
unsigned long Partition(unsigned long *p,unsigned long low,unsigned long high) //divide data
{
unsigned long pivotkey=p[low];
while(low<high)
{
while(low<high&&p[high]>=pivotkey)
high--;
xchg(&p[low],&p[high]);
while(low<high&&p[low]<=pivotkey)
low++;
xchg(&p[low],&p[high]);
}
return low;
}
void Qsort(unsigned long *p,unsigned long low,unsigned long high) //quicksort function
{
if(low<high)
{
unsigned long pivotloc=Partition(p,low,high);
Qsort(p,low,pivotloc-1);
Qsort(p,pivotloc+1,high);
}
}
DWORD WINAPI sort(LPVOID ptr)
{
unsigned long *p=(unsigned long *)ptr;
unsigned long n=*(p+1)-*p+1;
tflag++;
HANDLE hthread=NULL;
if(n<=5||threadnum>20)
{
Qsort((unsigned long *)pmem,*(p),*(p+1));
}
else
{
DWORD threadid[2];
unsigned long *param1=new DWORD [2];
unsigned long *param2=new DWORD [2];
unsigned long pivotloc=Partition((unsigned long *)pmem,*(p),*(p+1));
param1[0]=*p;
param1[1]=pivotloc-1;
param2[0]=pivotloc+1;
param2[1]=*(p+1);
delete []ptr;
if((pivotloc-1)>*p && pivotloc>0)
{
hthread=CreateThread(NULL,NULL,&sort,param1,0,&threadid[1]);
if(hthread==NULL)
{
MessageBox(NULL,"thread create error","note",MB_OK);
return 1;
}
threadnum++;
tflag++;
CloseHandle(hthread);
}
if((pivotloc+1)<*(p+1))
{
hthread=CreateThread(NULL,NULL,&sort,param2,0,&threadid[2]);
if(hthread==NULL)
{
MessageBox(NULL,"thread create error","note",MB_OK);
return 1;
}
threadnum++;
tflag++;
CloseHandle(hthread);
}
}
tflag--;
return 0;
}
the target file have 10 unsigned long numbers for the test.
the multithreading debug makes me CRAZY!:(
thanks again
