PageSourceSearch

https://rogerdahl.github.io/cuda/collatz/index.html

html rogerdahl.github.io collected 2026-10-03 09:51:40 UTC 25,911 bytes, 383 lines download raw bytes

1<!DOCTYPE html>
2
3
4<html xmlns="http://www.w3.org/1999/xhtml">
5  <head>
6    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
7    
8    <title>CUDA Collatz &mdash; dahlsys.com</title>
9    
10    <link rel="stylesheet" href="../../_static/f6.css" type="text/css" />
11    <link rel="stylesheet" href="../../_static/pygments.css" type="text/css" />
12    
13    
13<script type="text/javascript">
14      var DOCUMENTATION_OPTIONS = {
15        URL_ROOT:    '../../',
16        VERSION:     '1.0',
17        COLLAPSE_INDEX: false,
18        FILE_SUFFIX: '.html',
19        HAS_SOURCE:  true
20      };
21    </script>
21
22    
22<script type="text/javascript" src="../../_static/jquery.js"></script>
22
23    
23<script type="text/javascript" src="../../_static/underscore.js"></script>
23
24    
24<script type="text/javascript" src="../../_static/doctools.js"></script>
24
25    <link rel="top" title="dahlsys.com" href="../../index.html" />
26    <link rel="up" title="CUDA" href="../../index_cuda.html" />
27    <link rel="next" title="CUDA Overcomplete Wavelet (OW) Filter" href="../overcomplete_wavelet/index.html" />
28    <link rel="prev" title="CUDA Benoit" href="../benoit/index.html" /><link href='http://fonts.googleapis.com/css?family=Source+Sans+Pro:300,400,600,300italic,400italic,600italic|Source+Code+Pro' rel='stylesheet' type='text/css'>
29
30<!-- Piwik -->
31<script type="text/javascript">
32  var _paq = _paq || [];
33  _paq.push(['trackPageView']);
34  _paq.push(['enableLinkTracking']);
35  (function() {
36    var u="//rd.gnus.org/analytics/";
37    _paq.push(['setTrackerUrl', u+'piwik.php']);
38    _paq.push(['setSiteId', 2]);
39    var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0];
40    g.type='text/javascript'; g.async=true; g.defer=true; g.src=u+'piwik.js'; s.parentNode.insertBefore(g,s);
41  })();
42</script>
42
43<noscript><p><img src="//rd.gnus.org/analytics/piwik.php?idsite=1" style="border:0;" alt="" /></p></noscript>
44<!-- End Piwik Code -->
45  </head>
46  <body role="document">
47    <div class="related" role="navigation" aria-label="related navigation">
48      <h3>Navigation</h3>
49      <ul>
50        <li class="right" style="margin-right: 10px">
51          <a href="../../genindex.html" title="General Index"
52             accesskey="I">index</a></li>
53        <li class="right" >
54          <a href="../overcomplete_wavelet/index.html" title="CUDA Overcomplete Wavelet (OW) Filter"
55             accesskey="N">next</a> |</li>
56        <li class="right" >
57          <a href="../benoit/index.html" title="CUDA Benoit"
58             accesskey="P">previous</a> |</li>
59        <li class="nav-item nav-item-0"><a href="../../index.html">dahlsys.com</a> &raquo;</li>
60          <li class="nav-item nav-item-1"><a href="../../index_cuda.html" accesskey="U">CUDA</a> &raquo;</li> 
61      </ul>
62    </div>
63      <div class="sphinxsidebar" role="navigation" aria-label="main navigation">
64        <div class="sphinxsidebarwrapper">
65            <p class="logo"><a href="../../index.html">
66              <img class="logo" src="../../_static/b3-tran.png" alt="Logo"/>
67            </a></p>
68  
69  <h3><a href="../../index.html">Table Of Contents</a></h3>
70  <ul>
71<li><a class="reference internal" href="#">CUDA Collatz</a><ul>
72<li><a class="reference internal" href="#glossary">Glossary</a></li>
73<li><a class="reference internal" href="#overview-of-implemented-optimizations">Overview of implemented optimizations</a><ul>
74<li><a class="reference internal" href="#high-level-optimizations">High level optimizations</a><ul>
75<li><a class="reference internal" href="#skipping-n">Skipping <code class="docutils literal"><span class="pre">N</span></code></a></li>
76<li><a class="reference internal" href="#delay-calculation-optimizations"><code class="docutils literal"><span class="pre">Delay</span></code> calculation optimizations</a></li>
77</ul>
78</li>
79<li><a class="reference internal" href="#low-level-optimizations">Low Level optimizations</a></li>
80</ul>
81</li>
82<li><a class="reference internal" href="#sieve-generator">Sieve generator</a></li>
83<li><a class="reference internal" href="#todo">Todo</a></li>
84</ul>
85</li>
86</ul>
87
88
89  
90    <p>
91    
92      <hr><ul><li class="dl_l1">Download</li></ul>
93<ul class="current">
94<ul class="current">
95<li class="dl_l1_os">Windows 64<br><a href="/static/cuda_collatz_exe.7z">cuda_collatz_exe.7z</a></li>
96<li class="dl_l1_os">Source<br><a href="/static/cuda_collatz_src.7z">cuda_collatz_src.7z</a></li>
97</ul>
98</ul>
99
100    
101
102    
103      <p><ul><li class="dl_l1">Technologies</li></ul>
104<ul class="current">
105<ul class="current">
106<li class="dl_l2">C++</li>
107<li class="dl_l2">Boost</li>
108</ul>
109</ul>
110
111    
112
113    
114    </p>
115  
116
117  <p>
118  <ul>
119    <li class="dl_l1">Questions and Feedback</li></ul>
120    <ul class="current">
121    <ul class="current">
122      <li class="dl_l2"><a href="mailto:dahlsys at gmail.com">Email</a></li>
123    </ul>
124    </ul>
125  </p>
126
127  <h4>Previous topic</h4>
128  <p class="topless"><a href="../benoit/index.html"
129                        title="previous chapter">CUDA Benoit</a></p>
130  <h4>Next topic</h4>
131  <p class="topless"><a href="../overcomplete_wavelet/index.html"
132                        title="next chapter">CUDA Overcomplete Wavelet (OW) Filter</a></p>
133
134        </div>
135      </div>
136
137    <div class="document">
138  
139      <div class="documentwrapper">
140        <div class="bodywrapper">
141          <div class="body" role="main">
142            
143  <div class="section" id="cuda-collatz">
144<h1>CUDA Collatz<a class="headerlink" href="#cuda-collatz" title="Permalink to this headline">¶</a></h1>
145<p>See <a class="reference external" href="http://en.wikipedia.org/wiki/Collatz_conjecture">Wikipedia - Collatz Conjecture</a> and <a class="reference external" href="http://www.ericr.nl/wondrous/index.html">On the 3x + 1 problem</a> for more information about this
146intriguing mathematical problem.</p>
147<p>I think this might be the world&#8217;s fastest single chip Collatz <a class="reference internal" href="#term-delay-rec
147ord"><span class="xref std std-term">Delay
148Record</span></a> calculator. With starting numbers in the 64 bit range, this app checks
149around 8 billion numbers per second for <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>s on a GTX570
150graphics card.</p>
151<div class="section" id="glossary">
152<h2>Glossary<a class="headerlink" href="#glossary" title="Permalink to this headline">¶</a></h2>
153<dl class="glossary docutils">
154<dt id="term-n">N</dt>
155<dd>A positive number for which the <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> is to be calculated. In
156theory, it can be infinitely large, but this implementation limits starting
157<a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> to 64 bits and <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> that may be reached during the trajectory
158to 128 bits.</dd>
159<dt id="term-delay">Delay</dt>
160<dd>The number of iterations of the Collatz rules on a given <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> until the
161<a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> reaches the value 1.</dd>
162<dt id="term-trajectory">Trajectory</dt>
163<dd>The path a specific <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> follows from its first value until it reaches
164the value 1.</dd>
165<dt id="term-delay-class">Delay Class</dt>
166<dd>All numbers <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> that have a specific <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a>.</dd>
167<dt id="term-class-record">Class Record</dt>
168<dd><p class="first">The lowest <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> in a given <a class="reference internal" href="#term-delay-class"><span class="xref std std-term">Delay Class</span></a>.</p>
169<p class="last">The first <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> that we find that has a previously unencountered
170<a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> is a Class Record. If the <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> is also in the highest
171<a class="reference internal" href="#term-delay-class"><span class="xref std std-term">Delay Class</span></a>, it is also a <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>.</p>
172</dd>
173<dt id="term-delay-record">Delay Record</dt>
174<dd>The lowest <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> that has a <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> higher than the <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a>
175of the previous <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>.</dd>
176</dl>
177</div>
178<div class="section" id="overview-of-implemented-optimizations">
179<h2>Overview of implemented optimizations<a class="headerlink" href="#overview-of-implemented-optimizations" title="Permalink to this headline">¶</a></h2>
180<p>The performance of this app is achieved by a combination of high level and low
181level optimizations. What follows is brief overview of each optimization.</p>
182<div class="section" id="high-level-optimizations">
183<h3>High level optimizations<a class="headerlink" href="#high-level-optimizations" title="Permalink to this headline">¶</a></h3>
184<p>These optimizations are described on the <a class="reference external" href="http://en.wikipedia.org/wiki/Collatz_conjecture">Wikipedia - Collatz Conjecture</a> page.</p>
185<div class="section" id="skipping-n">
186<h4>Skipping <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a><a class="headerlink" href="#skipping-n" title="Permalink to this headline">¶</a></h4>
187<p>Many <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> can be ruled out as <a class="reference internal" href="#term-delay-rec
187ord"><span class="xref std std-term">Delay Record</span></a>s without calculating
188their <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a>s.</p>
189<ul>
190<li><p class="first">All even <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> are skipped because any even <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>
191can be derived directly from the previous odd numbered <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>.
192(Skips 50% of all <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a>.)</p>
193</li>
194<li><p class="first">All <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> on the form of 3k+2 (N is congruent 2 modulo 3) are
195skipped because these numbers are not potential <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>s.
196(Skips 33% of all remaining <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a>.)</p>
197</li>
198<li><p class="first">A table, called a sieve, is used to skip checking of many <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a>. The sieve
199checks whether paths come together. If two paths join then the upper one can
200never yield a <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a> (or Class Record) and can be skipped.
201(Skips approximately 80% of all remaining <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a>.)</p>
202<p>Example: Any <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> of the form 8k+4 will reach 6k+4 after 3 steps, and so
203will any <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> of the form 8k+5. Therefore no <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> of the form 8k+5
204can be a Class Record (5 itself being the only exception). So any <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> of
205the form 8k+5 does not need to be checked, and all positions of the form 8k+5
206in the sieve contain a zero.</p>
207</li>
208</ul>
209<p>After these optimization have been performed, Less than 7% of all <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a>
210remain to actually be calculated. So, while the app checks around 8 billion
211<a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a>s, it calculates the <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> of around 560 million <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> s.</p>
212</div>
213<div class="section" id="delay-calculation-optimizations">
214<h4><a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> calculation optimizations<a class="headerlink" href="#delay-calculation-optimizations" title="Permalink to this headline">¶</a></h4>
215<p>The <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> s for the <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> that were not skipped must be calculated.
216The following optimizations are done when calculating <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a>s.</p>
217<ul class="simple">
218<li>Lookup tables are used to perform multiple steps of the Collatz calculation
219per iteration of the calculation loop.</li>
220<li>A table, called a &#8220;tail&#8221;, is used to prevent having to calculate the
221<a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a>s of small Ns. Once <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> drops below a certain value, the
222final delay is calculated by looking the remaining <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> up in this
223table and adding it to the current <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a>.</li>
224<li>In addition, an early break technique has been tested. In this technique,
225<a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> is compared with known, earlier <a class="reference internal" href="#term-delay-rec
225ord"><span class="xref std std-term">Delay Record</span></a>s. Calculation
226is ended early when it is determined that <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> cannot possibly become a
227<a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>. Unfortunately, the speed increase from ending
228calculations early was outweighed by the overhead of continually checking
229<a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> against a table of <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>s, resulting in a net
230decrease of calculation speed. So, the early break optimization has been left
231in the code, but has been disabled.</li>
232</ul>
233</div>
234</div>
235<div class="section" id="low-level-optimizations">
236<h3>Low Level optimizations<a class="headerlink" href="#low-level-optimizations" title="Permalink to this headline">¶</a></h3>
237<p>These are specific to my CUDA implementation for the GPU.</p>
238<ul class="simple">
239<li>The sieve technique that is described on Wikipedia yields a table that
240contains a power-of-two number of entries. For instance, a 20 bit sieve
241contains 2^20 = 1,048,576 entries. The table is applicable to all Ns, to
242infinity. Each entry is a true/false value that describes if the corresponding
243<a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> modulus X can be skipped. In a straightforward GPU implementation,
244one would create 1,048,576 threads, have each check its true/false value in
245the table, and abort if the value is false. This would abort around 80% of the
246values, and calculations would proceed on 20%. On the GPU, threads are run in
247warps. A warp has to keep running as long as at least 1 thread is active. In
248general, each warp would have a few threads active after sieving, so there
249would be almost no speed advantage on the GPU. The most fun I had with this
250project was with finding out how to optimize this on the GPU. The solution
251turned out to be simple. All I had to do was to transform the table of
252true/false values to a table of offsets to all the true values. In this way,
253only the same number of threads as there were true values had to be started
254and no threads had to be aborted. Each thread determines which <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> it
255should calculate by using its index to look up the corresponding offset in the
256sieve offsets table and adding it to the base <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a>.</li>
257<li>Instead of individually performing the three steps described above that filter
258out <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> I rolled those filters into a combined table. Because one of the
259filters remove all numbers on the form 3k+2 (one number out of three), this
260was accomplished by creating three variations of the table, each filtering a
261different set of every three numbers and, for each block of <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> select
262the one that filters out the correct numbers for that <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a> base.</li>
263<li>The step algorithm requires two tables called c and d. It also requires that 3
264to-the-power of the lookup index be calculated for each lookup. Because the
265indexes into each of the tables and the index used in the 3 to-the-power-of
266calculation is the same for a given round in the loop, I created a table for
267the exp3 values and interleaved the three tables so that a single lookup could
268be used for finding both the c and d values and the 3exp value. I found that a
269step size of 19 is the largest step size in which none of the values in the
270tables overflow 32 bit values. The size of the step tables doubles for each
271additional step. 19 steps takes 2 ^ 19 * 4 * 4 = 8,388,608 bytes.</li>
272<li>The <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a> calculation loop was simplified by making sure that the step
273table is wider than the sieve bits.</li>
274<li>
274In C, there is no efficient way of doing math operations with higher bit width
275than what is natively supported by the machine (because C does not support an
276efficient way of capturing the carry flag and including it in new
277calculations.) The target GPU, GF110, is a 32 bit machine and this calculator
278does 128 bit calculations while calculating the <a class="reference internal" href="#term-delay"><span class="xref std std-term">Delay</span></a>, so it was
279written in PTX (A VM assembly language for NVIDIA GPUs). This helped speed up
280other operations as well.</li>
281</ul>
282</div>
283</div>
284<div class="section" id="sieve-generator">
285<h2>Sieve generator<a class="headerlink" href="#sieve-generator" title="Permalink to this headline">¶</a></h2>
286<p>As described above, the sieve is a precomputed table that specifies <a class="reference internal" href="#term-n"><span class="xref std std-term">N</span></a>
287for which no <a class="reference internal" href="#term-delay-record"><span class="xref std std-term">Delay Record</span></a>s are possible and thus, can be skipped.</p>
288<p>A 19 bit wide sieve turned out to be the optimal size in my GPU implementation.
289Initially, I thought that the optimal size for the sieve would be the widest
290sieve that would fit in GPU memory, so I went about creating an app that could
291create an arbitrarily wide sieve.</p>
292<p>Generating a small sieve is simple. To generate a sieve, say 10 bits wide, 1024k
293+ i is calculated, where i loops from 0 to 1023. 10 steps of x/2 or (3x+1)/2 are
294done. After that a number on the form 3^p + r is obtained. If some of those
295numbers end up with the same p and r, all of them can be skipped, except the
296lowest one.</p>
297<p>However, this method does not work for generating a large sieve. The reason is
298that the algorithm is slowed down by a <a class="reference external" href="http://en.wikipedia.org/wiki/Schlemiel_the_Painter%27s_algorithm">Schlemiel the Painter&#8217;s algorithm</a>. For each
299new entry in the table, the algorithm has to revisit all the previously
300generated entries. As the number of entries increases, the algorithm keeps
301slowing down, until it virtually grinds to a halt.</p>
302<p>By analyzing the algorithm, I found that it could be implemented in a way that
303does not require revisiting all the previously generated entries for each new
304entry. The new algorithm makes it feasible to create large sieves. It works by
305creating entries that can be sorted in such a way that only a single pass over
306all the records is necessary.</p>
307<p>A sieve that would use 2GB of memory covers 2 (because we remove even numbered
308bits in the end) * 2GB * 8 (bits per byte) = 32gbit = 2^35 = 34 359 738 368
309bits. To generate this sieve, it is necessary to have a sortable table with the
310same number of entries. Each entry is 16 bytes (optimized using bitfields). 16
311bytes * 34 359 738 368 entry = 512GB of temporary storage.</p>
312<p>Unless one has a supercomputer with TBs of RAM, it is necessary to use disks for
313storage. I found a library called STXXL that implements STL for large datasets
314and includes algorithms that are efficient when using disk based storage. <a class="reference external" href="http://stxxl.sourceforge.net/">STXXL</a> enabled me to easily create an app that
315manipulates the data in much the same way as I would with regular STL. The
316stxxl::sort is not in-place. It requires the same amount of disk space as the
317size of the data being sorted, to store the sorted runs during sorting. So
318another 512GB is required during the step that sorts the entries.</p>
319<p>The same number of index records is also required, each is 64 bits + 8 bits = 9
320bytes. This is less than the extra memory used by sorting the Collatz records,
321so the peak disk usage is 1TB.</p>
322<p>Adding 20% for overhead, I determined that around 1.2TB of disk space was
323required to generate a 2^35 sieve. At the time when I did this project, disks
324weren&#8217;t that large, so I set up several of my largest disks in a JBOD
325configuration to hold the temporary data. The single file on there, that was
326over 1TB at one point, is still the biggest file I&#8217;ve seen. It took around two
327weeks to run the app, during which time the disks were working continuously.</p>
328</div>
329<div class="section" id="todo">
330<h2>Todo<a class="headerlink" href="#todo" title="Permalink to this headline">¶</a></h2>
331<ul class="simple">
332<li>There is one unused 32 bit word used for padding in the interleaved step
333table. It might be worth it to extend the exp3 to this word, so that more
334steps can be done in one iteration.</li>
335</ul>
336</div>
337</div>
338
339
340          </div>
341        </div>
342      </div>
343
344  
345
346<!-- begin htmlcommentbox.com -->
347 <div id="HCB_comment_box"><a href="http://www.htmlcommentbox.com">HTML Comment Box</a> is loading comments...</div>
348 <link rel="stylesheet" type="text/css" href="http://www.htmlcommentbox.com/static/skins/simple/shady.zip" />
349 
349<script type="text/javascript" language="javascript" id="hcb"> /*<!--*/ (function(){s=document.createElement("script");
350s.setAttribute("type","text/javascript");
351s.setAttribute("src", "http://www.htmlcommentbox.com/jread?page="+escape((typeof hcb_user !== "undefined" && hcb_user.PAGE)||(""+window.location)).replace("+","%2B")+"&mod=%241%24wq1rdBcg%24.kGkaTzWdQN3PfIcds/kK1"+"&opts=398&num=10");
352if (typeof s!="undefined") document.getElementsByTagName("head")[0].appendChild(s);
353})();
354 /*-->*/ </script>
354
355<!-- end htmlcommentbox.com -->
356
357  
358
359
360      <div class="clearer"></div>
361    </div>
362    <div class="related" role="navigation" aria-label="related navigation">
363      <h3>Navigation</h3>
364      <ul>
365        <li class="right" style="margin-right: 10px">
366          <a href="../../genindex.html" title="General Index"
367             >index</a></li>
368        <li class="right" >
369          <a href="../overcomplete_wavelet/index.html" title="CUDA Overcomplete Wavelet (OW) Filter"
370             >next</a> |</li>
371        <li class="right" >
372          <a href="../benoit/index.html" title="CUDA Benoit"
373             >previous</a> |</li>
374        <li class="nav-item nav-item-0"><a href="../../index.html">dahlsys.com</a> &raquo;</li>
375          <li class="nav-item nav-item-1"><a href="../../index_cuda.html" >CUDA</a> &raquo;</li> 
376      </ul>
377    </div>
378    <div class="footer">
379        &copy; Copyright 2010, dahlsys.com.
380    Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 1.3.6.Theme by <a href="http://github.com/vkvn">vkvn</a>
381    </div>
382  </body>
383</html>

Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.