कुंजी नियम केवल "कांटा है जब फोर्किंग ओवरहेड फोर्क के काम की मात्रा से बहुत छोटा है"। चूंकि फोर्किंग ओवरहेड आपके द्वारा उपयोग की जाने वाली विशिष्ट तकनीक की एक संपत्ति है, और इसलिए काम करने का प्रयास भी है, आपको कुछ समझ में यह अनुभवजन्य निर्धारित करना है। इस ट्रेडऑफ का प्रतिनिधित्व करने के लिए आप अपने कोड में निरंतर कुछ थ्रेसहोल्ड ट्यूनिंग स्थिरता के साथ समाप्त हो जाएंगे।
अभ्यास में आप क्या खोजेंगे यह है कि काम के अलग-अलग हिस्सों को ढूंढना वास्तव में कठिन है। यदि आप काम को छोटा कर देते हैं, तो उसे बहुत निर्भरता नहीं मिली है और इसके सभी इनपुट डेटाफ्लो तैयार होने के बाद आप इसे शेड्यूल कर सकते हैं। लेकिन छोटे टुकड़ों का आमतौर पर छोटे काम का मतलब होता है, और फोर्किंग ओवरहेड आमतौर पर लाभ को अस्वीकार करता है। यदि आप भाग को बड़ा बनाने की कोशिश करते हैं, तो उनके पास इतनी सारी निर्भरताएं हैं कि आप उन्हें निर्धारित करने के लिए उन्हें तोड़ नहीं सकते हैं।
कुछ लोग भाग्यशाली हैं और ऐसे बड़े हिस्से मिल सकते हैं; हम उन अधिकांश भौतिकविदों और/या फोरट्रान प्रोग्रामर को बुलाते हैं और वे दुनिया को अलग-अलग टुकड़ों में विभाजित करके प्रेरित समानांतरता का लाभ उठा रहे हैं।
एकमात्र सभ्य इलाज जिसे मैं जानता हूं वह एक शानदार तेजी से फोर्किंग तंत्र का उपयोग करना है, ताकि आप सबसे छोटे व्यावहारिक हिस्सों को पा सकें। दुर्भाग्यवश, समांतरता पुस्तकालयों को ऐसा करने की पेशकश की गई है ... पुस्तकालयों, गतिशील रूप से लागू, गतिशील चालान ओवरहेड के साथ। समांतरता प्राइमेटिव युक्त विशिष्ट पुस्तकालयों में "कांटा" को लागू करने के लिए हजारों चक्रों में 100 से अधिक चक्र होते हैं; यदि आपके काम का हिस्सा 100 मशीन निर्देश है तो यह बुरी खबर है।
मुझे विश्वास है कि इस तरह के तेज फोर्किंग तंत्र प्राप्त करने के लिए, भाषा संकलक को यह जानना है कि आप कांटा कर रहे हैं, उदाहरण के लिए, "कांटा" (हालांकि वर्तनी :-) भाषा में एक कीवर्ड है। फिर संकलक कांटेदार देख सकते हैं, और इसे पूरा करने के लिए समय को कम करने के लिए आवश्यक सब कुछ आवंटित कर सकते हैं, और फोर्किंग (और शामिल) चरणों को प्रबंधित करने के लिए विशेष कोड उत्पन्न कर सकते हैं।
PARLANSE भाषा जिसे मैंने डिज़ाइन किया है, और हम अर्थात् डिजाइन में उपयोग करते हैं, ऐसी एक भाषा है। यह वाक्यविन्यास में एक लिस्प जैसी भाषा है (लेकिन अर्थशास्त्र में नहीं)। इसके समांतरता ऑपरेटर को लिखा गया है "(|| ...)"। आप नीचे दिए गए क्विक्सोर्ट मॉड्यूल में इसे नीचे देख सकते हैं। आप स्पष्ट QuickSortParallelThreshold मान भी देख सकते हैं, जो अनुभवी निर्धारित है। यह क्विक्सोर्ट एक इंटेल x86 सिस्टम पर रैखिक रूप से 8 कोर तक स्केल करता है।
(define QuickSort
(module
(;; (define Value nu)
(compileifthen (~ (defined QuickSortWithParlanseBuiltInOrderingOfNu))
(define QuickSortWithParlanseBuiltInOrderingOfNu ~f) ; use PARLANSE comparison operators
)compileifthen
(compileifthen (~ (defined QuickSortParallelThreshold))
(define QuickSortParallelThreshold 100)
)compileifthen
(compileifthen (~ (defined QuickSortThreshold))
(compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(define QuickSortThreshold 16)
(define QuickSortThreshold 8)
)compileifthenelse
)compileifthen
(compileifthenelse (~ (defined QuickSortWithCompareByReference))
(define QuickSortWithCompareByReference ~f)
(compileifthen QuickSortWithParlanseBuiltInOrderingOfNu
(define QuickSortWithCompareByReference ~f)
)compileifthen
)compileifthenelse
(define SortRange
(action (procedure (structure (compileifthen (~ QuickSortWithParlanseBuiltInOrderingOfNu)
(compileifthenelse (~ QuickSortWithCompareByReference)
[compare (function (sort integer (range -1 +1)) (structure [value1 Value] [value2 Value]))]
[compare (function (sort integer (range -1 +1)) (structure [value1 (reference Value)] [value2 (reference Value)]))]
)compileifthenelse
)compileifthen
[a (reference (array Value 1 dynamic))]
[from natural]
[to natural]
)structure
)procedure
(local (;; (define quicksort
(action (procedure (structure [l integer] [r integer])))
)define
(define quicksort
(action (procedure (structure [l integer] [r integer]))
(ifthenelse (<= (- r l) (coerce integer QuickSortThreshold))
(do [i integer] (++ l) r +1
(local (= [exch Value] a:i)
(block exit_if_inserted
(;; (do [j integer] (-- i) l -1
(ifthenelse (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(> a:j exch)
(compileifthenelse (~ QuickSortWithCompareByReference)
(== (compare a:j exch) +1)
(== (compare (. a:j) (. exch)) +1)
)compileifthenelse
)compileifthenelse
(= a:(++ j) a:j)
(;; (= a:(++ j) exch)
(exitblock exit_if_inserted)
);;
)ifthenelse
)do
(= a:l exch)
);;
)block
)local
)do
(local (;; (= [i integer] l)
(= [j integer] r)
(= [p integer] l)
(= [q integer] r)
[exch Value]
);;
(;;
`use middle element as pivot':
(local (= [m integer] (// (+ l r) +2))
(;; (= exch a:m)
(= a:m a:r)
(= a:r exch)
);;
)local
`4-way partitioning = < > =':
(loop exit_if_partitioned
(;;
`find element greater than pivot':
(loop exit_if_greater_than_found
(;; (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(ifthenelse (< a:i a:r)
(consume ~t)
(ifthenelse (> a:i a:r)
(exitblock exit_if_greater_than_found)
(;; (ifthen (>= i j)
(exitblock exit_if_partitioned)
)ifthen
(= exch a:p)
(= a:p a:i)
(= a:i exch)
(+= p 1)
);;
)ifthenelse
)ifthenelse
(case (compileifthenelse (~ QuickSortWithCompareByReference)
(compare a:i a:r)
(compare (. a:i) (. a:r))
)compileifthenelse
-1
(consume ~t)
+1
(exitblock exit_if_greater_than_found)
else (;; (ifthen (>= i j)
(exitblock exit_if_partitioned)
)ifthen
(= exch a:p)
(= a:p a:i)
(= a:i exch)
(+= p 1)
);;
)case
)compileifthenelse
(+= i 1)
);;
)loop
`find element less than to pivot':
(loop exit_if_less_than_found
(;; (-= j 1)
(ifthen (>= i j)
(exitblock exit_if_partitioned)
)ifthen
(compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(ifthenelse (< a:j a:r)
(exitblock exit_if_less_than_found)
(ifthenelse (> a:j a:r)
(consume ~t)
(;; (-= q 1)
(= exch a:j)
(= a:j a:q)
(= a:q exch)
);;
)ifthenelse
)ifthenelse
(case (compileifthenelse (~ QuickSortWithCompareByReference)
(compare a:j a:r)
(compare (. a:j) (. a:r))
)compileifthenelse
-1
(exitblock exit_if_less_than_found)
+1
(consume ~t)
else (;; (-= q 1)
(= exch a:j)
(= a:j a:q)
(= a:q exch)
);;
)case
)compileifthenelse
);;
)loop
`move found elements to proper partitions':
(;; (= exch a:i)
(= a:i a:j)
(= a:j exch)
);;
`increment index':
(+= i 1)
);;
)loop
`3-way partitioning <=>':
(;;
`move pivot to final location':
(;; (= exch a:i)
(= a:i a:r)
(= a:r exch)
(= j (-- i))
(= i (++ i))
);;
`move elements equal to pivot to final locations':
(;; (do [k integer] l (-- p) +1
(;; (= exch a:k)
(= a:k a:j)
(= a:j exch)
(-= j 1)
);;
)do
(do [k integer] (-- r) q -1
(;; (= exch a:i)
(= a:i a:k)
(= a:k exch)
(+= i 1)
);;
)do
);;
);;
`sort partitions not equal to pivot':
(ifthenelse (<= (- r l) (coerce integer QuickSortParallelThreshold))
(;; (quicksort l j)
(quicksort i r)
);;
(|| (quicksort l j)
(quicksort i r)
)||
)ifthenelse
);;
)local
)ifthenelse
)action
)define
);;
(;; (quicksort (coerce integer from) (coerce integer to))
(ifdebug (do [i integer] (coerce integer from) (-- (coerce integer to)) +1
(trust (compileifthenelse QuickSortWithParlanseBuiltInOrderingOfNu
(<= a:i a:(++ i))
(compileifthenelse (~ QuickSortWithCompareByReference)
(<= (compare a:i a:(++ i)) +0)
(<= (compare (. a:i) (. a:(++ i))) +0)
)compileifthenelse
)compileifthenelse
`QuickSort:Sort -> The array is not sorted.'
)trust
)do
)ifdebug
);;
)local
)action
)define
(define Sort
(action (procedure (structure (compileifthen (~ QuickSortWithParlanseBuiltInOrderingOfNu)
(compileifthenelse (~ QuickSortWithCompareByReference)
[compare (function (sort integer (range -1 +1)) (structure [value1 Value] [value2 Value]))]
[compare (function (sort integer (range -1 +1)) (structure [value1 (reference Value)] [value2 (reference Value)]))]
)compileifthenelse
)compileifthen
[a (reference (array Value 1 dynamic))]
)structure
)procedure
(compileifthenelse (~ QuickSortWithParlanseBuiltInOrderingOfNu)
(SortRange compare a (coerce natural (lowerbound (@ a) 1)) (coerce natural (upperbound (@ a) 1)))
(SortRange a (coerce natural (lowerbound (@ a) 1)) (coerce natural (upperbound (@ a) 1)))
)compileifthenelse
)action
)define
);;
)module
)define
उत्तर देने के लिए कठिन सवाल - वास्तव में समस्या डोमेन और हार्डवेयर बाधाओं पर निर्भर करता है I - क्रमबद्ध करें - आप कितने आइटम सॉर्ट कर रहे हैं और किस हार्डवेयर पर – zebrabox