Merge algorithm - Revision history

CiaPan: /* Application */ adjusting grammatical number of verbs to plural 'arrows'

2024-11-14T11:53:17Z

Application: adjusting grammatical number of verbs to plural 'arrows'

← Previous revision		Revision as of 11:53, 14 November 2024
Line 3:		Line 3:

	== Application ==		== Application ==
	[[File:Merge sort algorithm diagram.svg\|thumb\|upright=1.5\|A graph exemplifying merge sort. Two red arrows starting from the same node ~~indicates~~ ~~subdivision~~, while two green arrows ending in the same node ~~corresponds~~ to an execution of the merge algorithm.]]		[[File:Merge sort algorithm diagram.svg\|thumb\|upright=1.5\|A graph exemplifying merge sort. Two red arrows starting from the same node indicate a split, while two green arrows ending at the same node correspond to an execution of the merge algorithm.]]
	The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort\|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:		The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort\|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:

CiaPan: Reverted 1 edit by BlåhajProgramming (talk): WP:OR + false claim about algorithm's behavior with both arrays having the size of 1

2024-11-08T09:49:13Z

Reverted 1 edit by BlåhajProgramming (talk): WP:OR + false claim about algorithm's behavior with both arrays having the size of 1

← Previous revision		Revision as of 09:49, 8 November 2024
Line 97:		Line 97:

	'''if''' m < n '''then'''		'''if''' m < n '''then'''
	~~''merge(B[k...ℓ], A[i...j], C[p...q]) // swaps~~ A and B to ensure that A is the larger array''		swap A and B ''// ensure that A is the larger array: i, j still belong to A; k, ℓ to B''
	~~'''return'''~~		swap m and n

	'''if''' m < 0 '''then'''		'''if''' m ≤ 0 '''then'''
	'''return''' ''// base case, nothing to merge''		'''return''' ''// base case, nothing to merge''

	'''let''' r = ⌊(i + j)/2⌋		'''let''' r = ⌊(i + j)/2⌋
	'''let''' s = binary-search(A[r], B[k...ℓ]) ~~''// index where B[k...s] ≤ A[r] ≤ B[s...l] for all values''~~		'''let''' s = binary-search(A[r], B[k...ℓ])
	'''let''' t = p + (r - i) + (s - k)		'''let''' t = p + (r - i) + (s - k)
	C[t] = A[r]		C[t] = A[r]

	'''in parallel do'''		'''in parallel do'''
	merge(A[i...r-1], B[k...s-1], C[p...t-1]) ~~''// all values are smaller or equal to A[r]''~~		merge(A[i...r], B[k...s], C[p...t])
	merge(A[r+1...j], B[s...ℓ], C[t+1...q]) ~~''// all values are greater or equal to A[r]''~~		merge(A[r+1...j], B[s...ℓ], C[t+1...q])

	The algorithm operates by splitting either {{mvar\|A}} or {{mvar\|B}}, whichever is larger, into (nearly) equal halves. It then splits the other array into a part with values smaller than the midpoint of the first, and a part with larger or equal values. (The [[binary search]] subroutine returns the index in {{mvar\|B}} where {{math\|''A''[''r'']}} would be, if it were in {{mvar\|B}}; that this always a number between {{mvar\|k}} and {{mvar\|ℓ}}.) Finally, each pair of halves is merged [[Divide and conquer algorithm\|recursively]], and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <ref name="vjd">{{citation\| author=Victor J. Duvanenko\| title=Parallel Merge\| journal=Dr. Dobb's Journal\| date=2011\| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>		The algorithm operates by splitting either {{mvar\|A}} or {{mvar\|B}}, whichever is larger, into (nearly) equal halves. It then splits the other array into a part with values smaller than the midpoint of the first, and a part with larger or equal values. (The [[binary search]] subroutine returns the index in {{mvar\|B}} where {{math\|''A''[''r'']}} would be, if it were in {{mvar\|B}}; that this always a number between {{mvar\|k}} and {{mvar\|ℓ}}.) Finally, each pair of halves is merged [[Divide and conquer algorithm\|recursively]], and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <ref name="vjd">{{citation\| author=Victor J. Duvanenko\| title=Parallel Merge\| journal=Dr. Dobb's Journal\| date=2011\| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>

BlåhajProgramming: Fixed bugs in the pseudocode for Paraler merge. originally it would fail when, for example if merge were given two arrays both having the size of 1 the psudo code would immediately exit without saving the result or sorting it. There was also an infinite loop that results in stackoverflow whenever A[r] is the largest value in both arrays.

2024-11-08T05:07:12Z

Fixed bugs in the pseudocode for Paraler merge. originally it would fail when, for example if merge were given two arrays both having the size of 1 the psudo code would immediately exit without saving the result or sorting it. There was also an infinite loop that results in stackoverflow whenever A[r] is the largest value in both arrays.

← Previous revision		Revision as of 05:07, 8 November 2024
Line 97:		Line 97:

	'''if''' m < n '''then'''		'''if''' m < n '''then'''
	~~swap~~ A and B ~~''//~~ ensure that A is the larger array~~: i, j still belong to A; k, ℓ to B~~''		''merge(B[k...ℓ], A[i...j], C[p...q]) // swaps A and B to ensure that A is the larger array''
	~~swap m and n~~		'''return'''

	'''if''' m ≤ 0 '''then'''		'''if''' m < 0 '''then'''
	'''return''' ''// base case, nothing to merge''		'''return''' ''// base case, nothing to merge''

	'''let''' r = ⌊(i + j)/2⌋		'''let''' r = ⌊(i + j)/2⌋
	'''let''' s = binary-search(A[r], B[k...ℓ])		'''let''' s = binary-search(A[r], B[k...ℓ]) ''// index where B[k...s] ≤ A[r] ≤ B[s...l] for all values''
	'''let''' t = p + (r - i) + (s - k)		'''let''' t = p + (r - i) + (s - k)
	C[t] = A[r]		C[t] = A[r]

	'''in parallel do'''		'''in parallel do'''
	merge(A[i...r], B[k...s], C[p...t])		merge(A[i...r-1], B[k...s-1], C[p...t-1]) ''// all values are smaller or equal to A[r]''
	merge(A[r+1...j], B[s...ℓ], C[t+1...q])		merge(A[r+1...j], B[s...ℓ], C[t+1...q]) ''// all values are greater or equal to A[r]''

	The algorithm operates by splitting either {{mvar\|A}} or {{mvar\|B}}, whichever is larger, into (nearly) equal halves. It then splits the other array into a part with values smaller than the midpoint of the first, and a part with larger or equal values. (The [[binary search]] subroutine returns the index in {{mvar\|B}} where {{math\|''A''[''r'']}} would be, if it were in {{mvar\|B}}; that this always a number between {{mvar\|k}} and {{mvar\|ℓ}}.) Finally, each pair of halves is merged [[Divide and conquer algorithm\|recursively]], and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <ref name="vjd">{{citation\| author=Victor J. Duvanenko\| title=Parallel Merge\| journal=Dr. Dobb's Journal\| date=2011\| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>		The algorithm operates by splitting either {{mvar\|A}} or {{mvar\|B}}, whichever is larger, into (nearly) equal halves. It then splits the other array into a part with values smaller than the midpoint of the first, and a part with larger or equal values. (The [[binary search]] subroutine returns the index in {{mvar\|B}} where {{math\|''A''[''r'']}} would be, if it were in {{mvar\|B}}; that this always a number between {{mvar\|k}} and {{mvar\|ℓ}}.) Finally, each pair of halves is merged [[Divide and conquer algorithm\|recursively]], and since the recursive calls are independent of each other, they can be done in parallel. Hybrid approach, where serial algorithm is used for recursion base case has been shown to perform well in practice <ref name="vjd">{{citation\| author=Victor J. Duvanenko\| title=Parallel Merge\| journal=Dr. Dobb's Journal\| date=2011\| url=http://www.drdobbs.com/parallel/parallel-merge/229204454}}</ref>

Kri: /* Application */Fixed typo

2023-08-24T07:02:04Z

Application: Fixed typo

← Previous revision		Revision as of 07:02, 24 August 2023
Line 3:		Line 3:

	== Application ==		== Application ==
	[[File:Merge sort algorithm diagram.svg\|thumb\|upright=1.5\|A graph exemplifying merge sort. Two red arrows starting from the same node ~~indicated~~ subdivision, while two green arrows ending in the same node corresponds to an execution of the merge algorithm.]]		[[File:Merge sort algorithm diagram.svg\|thumb\|upright=1.5\|A graph exemplifying merge sort. Two red arrows starting from the same node indicates subdivision, while two green arrows ending in the same node corresponds to an execution of the merge algorithm.]]
	The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort\|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:		The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort\|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:

Kri: /* Application */ Explained how the merge algorithm relates to merge sort.

2023-08-24T06:12:14Z

Application: Explained how the merge algorithm relates to merge sort.

← Previous revision		Revision as of 06:12, 24 August 2023
Line 3:		Line 3:

	== Application ==		== Application ==
	[[File:Merge sort algorithm diagram.svg\|thumb\|upright=1.5\|An ~~example~~ ~~for~~ merge sort]]		[[File:Merge sort algorithm diagram.svg\|thumb\|upright=1.5\|A graph exemplifying merge sort. Two red arrows starting from the same node indicated subdivision, while two green arrows ending in the same node corresponds to an execution of the merge algorithm.]]
	The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort\|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:		The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort\|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:

Citation bot: Alter: title, template type. Add: chapter. Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

2023-07-22T12:28:41Z

Alter: title, template type. Add: chapter. Removed parameters. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 12:28, 22 July 2023
Line 126:		Line 126:
	There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.		There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.

	Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509\|hdl=10044/1/95271 \|s2cid=245669103 \|hdl-access=free }}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite ~~journal~~ \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title~~=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal~~=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038\|isbn=978-1-5386-5522-1 \|s2cid=52195866 }}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.		Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509\|hdl=10044/1/95271 \|s2cid=245669103 \|hdl-access=free }}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite book \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|chapter=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038\|isbn=978-1-5386-5522-1 \|s2cid=52195866 }}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.

	== Language support ==		== Language support ==

Citation bot: Add: isbn, s2cid. | Use this bot. Report bugs. | #UCB_CommandLine

2023-07-22T04:09:16Z

Add: isbn, s2cid. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 04:09, 22 July 2023
Line 126:		Line 126:
	There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.		There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.

	Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509\|hdl=10044/1/95271 \|hdl-access=free }}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite journal \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038}}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.		Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509\|hdl=10044/1/95271 \|s2cid=245669103 \|hdl-access=free }}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite journal \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038\|isbn=978-1-5386-5522-1 \|s2cid=52195866 }}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.

	== Language support ==		== Language support ==

OAbot: Open access bot: hdl added to citation with #oabot.

2023-01-30T07:45:16Z

Open access bot: hdl added to citation with #oabot.

← Previous revision		Revision as of 07:45, 30 January 2023
Line 126:		Line 126:
	There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.		There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.

	Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509}}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite journal \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038}}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.		Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509\|hdl=10044/1/95271 \|hdl-access=free }}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite journal \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038}}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.

	== Language support ==		== Language support ==

WikiCleanerBot: v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

2022-10-09T09:59:33Z

v2.05b - Bot T20 CW#61 - Fix errors for CW project (Reference before punctuation)

← Previous revision		Revision as of 09:59, 9 October 2022
Line 126:		Line 126:
	There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.		There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.

	Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]] <ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509}}</ref>. In 2018, Saitoh M. et al. introduced MMS <ref>{{cite journal \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038}}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.		Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]].<ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509}}</ref> In 2018, Saitoh M. et al. introduced MMS <ref>{{cite journal \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038}}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.

	== Language support ==		== Language support ==

86.188.218.117: fixed minor referencing issue of last edit

2022-10-06T08:33:12Z

fixed minor referencing issue of last edit

← Previous revision		Revision as of 08:33, 6 October 2022
Line 126:		Line 126:
	There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.		There are also algorithms that introduce parallelism within a single instance of merging of two sorted lists. These can be used in field-programmable gate arrays ([[FPGA]]s), specialized sorting circuits, as well as in modern processors with single-instruction multiple-data ([[SIMD]]) instructions.

	Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]]. In 2018, Saitoh M. et al introduced MMS <ref>{{cite journal \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038}}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref~~>{{cite~~ ~~journal \|last1~~=~~Papaphilippou~~ \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/~~TC.2022.3146509}}</ref~~> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.		Existing parallel algorithms are based on modifications of the merge part of either the [[bitonic sorter]] or [[odd-even mergesort]] <ref name="flimsj">{{cite journal \|last1=Papaphilippou \|first1=Philippos \|last2=Luk \|first2=Wayne \|last3=Brooks \|first3=Chris \|title=FLiMS: a Fast Lightweight 2-way Merger for Sorting \|journal=IEEE Transactions on Computers \|date=2022 \|pages=1–12 \|doi=10.1109/TC.2022.3146509}}</ref>. In 2018, Saitoh M. et al. introduced MMS <ref>{{cite journal \|last1=Saitoh \|first1=Makoto \|last2=Elsayed \|first2=Elsayed A. \|last3=Chu \|first3=Thiem Van \|last4=Mashimo \|first4=Susumu \|last5=Kise \|first5=Kenji \|title=A High-Performance and Cost-Effective Hardware Merge Sorter without Feedback Datapath \|journal=2018 IEEE 26th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM) \|date=April 2018 \|pages=197–204 \|doi=10.1109/FCCM.2018.00038}}</ref> for FPGAs, which focused on removing a multi-cycle feedback datapath that prevented efficient pipelining in hardware. Also in 2018, Papaphilippou P. et al. introduced FLiMS <ref name="flimsj" /> that improved the hardware utilization and performance by only requiring <math>\log_2(P)+1</math> pipeline stages of {{math\|''P/2''}} compare-and-swap units to merge with a parallelism of {{math\|''P''}} elements per FPGA cycle.

	== Language support ==		== Language support ==