स्टेंसिल और स्लाइडिंग विंडो

stencil हर output की गणना inputs के एक निश्चित neighborhood से करता है, जैसे किसी pixel का उसके आसपास की cells के साथ औसत निकालना।

जैसे-जैसे आप array में आगे बढ़ते हैं, input window एक स्थान से slides करती है। लगातार आने वाले outputs अपने अधिकांश inputs साझा करते हैं, इसलिए reuse बहुत अधिक होता है।

Neighbors overlap करते हैं, इसलिए एक बार load किया गया tile many outputs के लिए उपयोगी होता है। Stencils इसका textbook उदाहरण हैं कि tiling कहाँ प्रभावी होती है।

Tile के किनारों की गणना के लिए आपको उसके outside के कुछ elements भी चाहिए। इन अतिरिक्त border cells को halo कहा जाता है।

Tile के पहले thread को अपना left neighbor चाहिए, जो previous tile का हिस्सा है। Halo cells के बिना वह read गलत होगा।

Radius-r stencil के लिए हर side पर r extra cells load करें। 3-point blur का radius 1 होता है, इसलिए हर side पर एक halo cell पर्याप्त है।

Shared memory को blockDim plus 2 * radius के रूप में घोषित करें, ताकि interior और दोनों halos एक व्यवस्थित buffer में समा जाएँ।

हर thread पहले अपने element को tile में radius offset पर load करता है, जिससे सामने left halo के लिए जगह बची रहती है।

पहले कुछ threads double duty करते हैं और block के synchronize होने से पहले left और right halo cells भी लाते हैं।

__syncthreads के बाद हर thread अपने neighbors को पूरी तरह tile से पढ़ता है और उस step के लिए global memory को फिर कभी नहीं छूता।

अब हर interior value एक shared-memory load से 2r + 1 outputs को सेवा देती है। यही वह redundant traffic है जिसे tiling हटाती है।

Stencils overlapping windows पर slide करते हैं, इसलिए हर side पर r अतिरिक्त cells वाला halo tile को हर output के लिए एक-एक load के साथ सेवा देने देता है। ✅