PageSourceSearch

https://www.jasondavies.com/2026/tenstorrent-gcd/

html jasondavies.com collected 2026-09-24 09:00:39 UTC 22,293 bytes, 372 lines download raw bytes

1<!DOCTYPE html>
2<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
3<head>
4  <meta charset="utf-8" />
5  <meta name="generator" content="pandoc" />
6  <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
7  <title>Greatest Common Divisor on Tenstorrent</title>
8  <style>
9    code{white-space: pre-wrap;}
10    span.smallcaps{font-variant: small-caps;}
11    div.columns{display: flex; gap: min(4vw, 1.5em);}
12    div.column{flex: auto; overflow-x: auto;}
13    div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
14    /* The extra [class] is a hack that increases specificity enough to
15       override a similar rule in reveal.js */
16    ul.task-list[class]{list-style: none;}
17    ul.task-list li input[type="checkbox"] {
18      font-size: inherit;
19      width: 0.8em;
20      margin: 0 0.8em 0.2em -1.6em;
21      vertical-align: middle;
22    }
23    /* CSS for syntax highlighting */
24    html { -webkit-text-size-adjust: 100%; }
25    pre > code.sourceCode { white-space: pre; position: relative; }
26    pre > code.sourceCode > span { display: inline-block; line-height: 1.25; }
27    pre > code.sourceCode > span:empty { height: 1.2em; }
28    .sourceCode { overflow: visible; }
29    code.sourceCode > span { color: inherit; text-decoration: inherit; }
30    div.sourceCode { margin: 1em 0; }
31    pre.sourceCode { margin: 0; }
32    @media screen {
33    div.sourceCode { overflow: auto; }
34    }
35    @media print {
36    pre > code.sourceCode { white-space: pre-wrap; }
37    pre > code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
38    }
39    pre.numberSource code
40      { counter-reset: source-line 0; }
41    pre.numberSource code > span
42      { position: relative; left: -4em; counter-increment: source-line; }
43    pre.numberSource code > span > a:first-child::before
44      { content: counter(source-line);
45        position: relative; left: -1em; text-align: right; vertical-align: baseline;
46        border: none; display: inline-block;
47        -webkit-touch-callout: none; -webkit-user-select: none;
48        -khtml-user-select: none; -moz-user-select: none;
49        -ms-user-select: none; user-select: none;
50        padding: 0 4px; width: 4em;
51        color: #aaaaaa;
52      }
53    pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa;  padding-left: 4px; }
54    div.sourceCode
55      {   }
56    @media screen {
57    pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; }
58    }
59    code span.al { color: #ff0000; font-weight: bold; } /* Alert */
60    code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
61    code span.at { color: #7d9029; } /* Attribute */
62    code span.bn { color: #40a070; } /* BaseN */
63    code span.bu { color: #008000; } /* BuiltIn */
64    code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
65    code span.ch { color: #4070a0; } /* Char */
66    code span.cn { color: #880000; } /* Constant */
67    code span.co { color: #60a0b0; font-style: italic; } /* Comment */
68    code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
69    code span.do { color: #ba2121; font-style: italic; } /* Documentation */
70    code span.dt { color: #902000; } /* DataType */
71    code span.dv { color: #40a070; } /* DecVal */
72    code span.er { color: #ff0000; font-weight: bold; } /* Error */
73    code span.ex { } /* Extension */
74    code span.fl { color: #40a070; } /* Float */
75    code span.fu { color: #06287e; } /* Function */
76    code span.im { color: #008000; font-weight: bold; } /* Import */
77    code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
78    code span.kw { color: #007020; font-weight: bold; } /* Keyword */
79    code span.op { color: #666666; } /* Operator */
80    code span.ot { color: #007020; } /* Other */
81    code span.pp { color: #bc7a00; } /* Preprocessor */
82    code span.sc { color: #4070a0; } /* SpecialChar */
83    code span.ss { color: #bb6688; } /* SpecialString */
84    code span.st { color: #4070a0; } /* String */
85    code span.va { color: #19177c; } /* Variable */
86    code span.vs { color: #4070a0; } /* VerbatimString */
87    code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
88  </style>
89  <link rel="stylesheet" href="water.css" />
90  <meta property="og:title" content="Greatest Common Divisor on Tenstorrent">
91  <meta property="og:image" content="https://www.jasondavies.com/2026/tenstorrent-gcd/full.png">
92  <meta property="twitter:card" content="summary_large_image">
93  <meta property="twitter:image" content="https://www.jasondavies.com/2026/tenstorrent-gcd/full.png">
94</head>
95<body>
96<header id="title-block-header">
97<h1 class="title">Greatest Common Divisor on Tenstorrent</h1>
98<p class="date">5th March, 2026</p>
99</header>
100<style>
101:root {
102  --gcd-code-active-bg: rgba(255, 235, 0, 0.32);
103  --gcd-code-active-outline: rgba(0, 0, 0, 0.24);
104}
105
106@media (prefers-color-scheme: dark) {
107  :root {
108    --gcd-code-active-bg: rgba(255, 235, 0, 0.28);
109    --gcd-code-active-outline: rgba(255, 255, 255, 0.28);
110  }
111}
112
113h1, .date {
114  text-align: center;
115}
116
117.gcd-demo {
118  margin: 0.55rem 0 0.9rem;
119  padding: 0;
120}
121
122.gcd-controls {
123  display: flex;
124  gap: 0.4rem;
125  margin-top: 0.3rem;
126  margin-bottom: 0;
127  align-items: center;
128}
129
130.gcd-controls button {
131  border: 1px solid #b5bdc7;
132  border-radius: 8px;
133  background: #ffffff;
134  color: #111827;
135  min-height: 1.75rem;
136  padding: 0.12rem 0.5rem;
137  display: inline-flex;
138  align-items: center;
139  justify-content: center;
140  cursor: pointer;
141}
142
143.gcd-controls button:disabled {
144  cursor: not-allowed;
145  opacity: 0.6;
146}
147
148.gcd-run-label {
149  display: block;
150  font-size: 0.92rem;
151  font-family: ui-monospace, SFMono-Regular, Menlo, Monaco, Consolas, "Liberation Mono", "Courier New", monospace;
152  color: inherit;
153  margin-bottom: 0.25rem;
154}
155
156.gcd-svg-host {
157  width: 100%;
158  padding-bottom: 0;
159}
160
161.gcd-svg-host svg {
162  display: block;
163  width: 100%;
164  min-width: 0;
165  height: auto;
166  --gcd-on: #f00;
167  --gcd-off: #fff;
168  --gcd-border: #000;
169  --gcd-separator: #000;
170  --gcd-ctz: #ff0;
171  --gcd-highlight-opacity: 1;
172}
173
174.gcd-svg-host svg .gcd-bit-fill,
175.gcd-svg-host svg .gcd-bit-highlight,
176.gcd-svg-host svg .gcd-entering-fill,
177.gcd-svg-host svg .gcd-divider-line,
178.gcd-svg-host svg .gcd-entering-line,
179.gcd-svg-host svg .gcd-outline {
180  vector-effect: non-scaling-stroke;
181}
182
183.gcd-svg-host svg .gcd-bit-fill {
184  fill: var(--gcd-off);
185  shape-rendering: crispEdges;
186}
187
188.gcd-svg-host svg .gcd-bit-fill.on {
189  fill: var(--gcd-on);
190}
191
192.gcd-svg-host svg .gcd-bit-highlight {
193  fill: var(--gcd-ctz);
194  opacity: var(--gcd-highlight-opacity);
195  shape-rendering: crispEdges;
196}
197
198.gcd-svg-host svg .gcd-entering-fill {
199  fill: var(--gcd-off);
200  shape-rendering: crispEdges;
201}
202
203.gcd-svg-host svg .gcd-divider-line {
204  stroke: var(--gcd-separator);
205  stroke-width: 1;
206  shape-rendering: crispEdges;
207}
208
209.gcd-svg-host svg .gcd-entering-line {
210  stroke: var(--gcd-separator);
211  stroke-width: 1;
212  shape-rendering: crispEdges;
213}
214
215.gcd-svg-host svg .gcd-outline {
216  fill: none;
217  stroke: var(--gcd-border);
218  stroke-width: 1.2;
219  shape-rendering: crispEdges;
220}
221
222.gcd-svg-host svg .gcd-row-label {
223  fill: #000;
224  font-size: 14px;
225  font-family: ui-monospace, SFMono-Regular, Menlo, Monaco, Consolas, "Liberation Mono", "Courier New", monospace;
226  dominant-baseline: middle;
227}
228
229[id^="cb"].active {
230  background: var(--gcd-code-active-bg);
231  box-shadow: inset 0 0 0 1px var(--gcd-code-active-outline);
232  border-radius: 2px;
233  transition: background-color 140ms linear, box-shadow 140ms linear;
234}
235</style>
236<h2 id="introduction">Introduction</h2>
237<p>Below we optimise <code>gcd(a, b)</code> for computing the <a
238href="https://en.wikipedia.org/wiki/Greatest_common_divisor">greatest
239common divisor</a> of two 32-bit signed integers on <a
240href="https://tenstorrent.com">Tenstorrent</a>’s AI accelerators.</p>
241<h2 id="steins-binary-gcd-algorithm">Stein’s Binary GCD Algorithm</h2>
242<p><a href="https://en.wikipedia.org/wiki/Binary_GCD_algorithm">Stein’s
243binary GCD algorithm</a> relies only on shifts, compares, and subtracts,
244and so is the obvious choice for Tenstorrent.</p>
245<p>Here’s one possible optimised implementation:</p>
246<div class="sourceCode" id="cb1"><pre
247class="sourceCode python"><code class="sourceCode python"><span id="cb1-1"><a href="#cb1-1" aria-hidden="true" tabindex="-1"></a><span class="kw">def</span> gcd(a: <span class="bu">int</span>, b: <span class="bu">int</span>) <span class="op">-&gt;</span> <span class="bu">int</span>:</span>
248<span id="cb1-2"><a href="#cb1-2" aria-hidden="true" tabindex="-1"></a>    a <span class="op">=</span> <span class="bu">abs</span>(a)</span>
249<span id="cb1-3"><a href="#cb1-3" aria-hidden="true" tabindex="-1"></a>    b <span class="op">=</span> <span class="bu">abs</span>(b)</span>
250<span id="cb1-4"><a href="#cb1-4" aria-hidden="true" tabindex="-1"></a>    k <span class="op">=</span> ctz(a <span class="op">|</span> b) <span class="co"># k = min(ctz(a), ctz(b))</span></span>
251<span id="cb1-5"><a href="#cb1-5" aria-hidden="true" tabindex="-1"></a></span>
252<span id="cb1-6"><a href="#cb1-6" aria-hidden="true" tabindex="-1"></a>    <span class="co"># ensure b is odd (if possible)</span></span>
253<span id="cb1-7"><a href="#cb1-7" aria-hidden="true" tabindex="-1"></a>    <span class="cf">if</span> (b <span class="op">&amp;</span> <span class="dv">1</span>) <span class="op">==</span> <span class="dv">0</span>:</span>
254<span id="cb1-8"><a href="#cb1-8" aria-hidden="true" tabindex="-1"></a>        a, b <span class="op">=</span> b, a</span>
255<span id="cb1-9"><a href="#cb1-9" aria-hidden="true" tabindex="-1"></a></span>
256<span id="cb1-10"><a href="#cb1-10" aria-hidden="true" tabindex="-1"></a>    <span class="cf">while</span> a <span class="op">!=</span> <span class="dv">0</span>:</span>
257<span id="cb1-11"><a href="#cb1-11" aria-hidden="true" tabindex="-1"></a>        a <span class="op">&gt;&gt;=</span> ctz(a)</span>
258<span id="cb1-12"><a href="#cb1-12" aria-hidden="true" tabindex="-1"></a>        <span class="cf">if</span> a <span class="op">&lt;</span> b:</span>
259<span id="cb1-13"><a href="#cb1-13" aria-hidden="true" tabindex="-1"></a>            a, b <span class="op">=</span> b, a</span>
260<span id="cb1-14"><a href="#cb1-14" aria-hidden="true" tabindex="-1"></a>        a <span class="op">-=</span> b</span>
261<span id="cb1-15"><a href="#cb1-15" aria-hidden="true" tabindex="-1"></a></span>
262<span id="cb1-16"><a href="#cb1-16" aria-hidden="true" tabindex="-1"></a>    <span class="cf">return</span> b <span class="op">&lt;&lt;</span> k</span></code></pre></div>
263<p>There is no direct <code>ctz</code> (count trailing zeros)
264instruction for Tenstorrent’s vector engine, but it does have <a
265href="https://github.com/tenstorrent/tt-isa-documentation/blob/main/WormholeB0/TensixTile/TensixCoprocessor/SFPLZ.md"><code>SFPLZ</code></a>
266(count leading zeros). Assuming non-zero <code>x</code>, we use the
267following:</p>
268<p><code>ctz(x) = 31 - clz(x &amp; -x)</code></p>
269<p>In assembly, this looks roughly like this:</p>
270<div class="sourceCode" id="cb2"><pre
271class="sourceCode asm"><code class="sourceCode fasm"><span id="cb2-1"><a href="#cb2-1" aria-hidden="true" tabindex="-1"></a>sfpmov  <span class="co">; y = x</span></span>
272<span id="cb2-2"><a href="#cb2-2" aria-hidden="true" tabindex="-1"></a>sfpiadd <span class="co">; y = -y</span></span>
273<span id="cb2-3"><a href="#cb2-3" aria-hidden="true" tabindex="-1"></a>sfpand  <span class="co">; y &amp;= x</span></span>
274<span id="cb2-4"><a href="#cb2-4" aria-hidden="true" tabindex="-1"></a>sfplz   <span class="co">; y = clz(y)</span></span>
275<span id="cb2-5"><a href="#cb2-5" aria-hidden="true" tabindex="-1"></a>sfpiadd <span class="co">; y = 31 - y</span></span></code></pre></div>
276<p>Since we have to perform a subtraction anyway, note that we can avoid
277the final <code>b &lt;&lt; k</code> by instead doing
278<code>a &gt;&gt;= ctz(a) - k</code> in the loop:</p>
279<div class="sourceCode" id="cb3"><pre
280class="sourceCode python"><code class="sourceCode python"><span id="cb3-1"><a href="#cb3-1" aria-hidden="true" tabindex="-1"></a><span class="kw">def</span> gcd(a: <span class="bu">int</span>, b: <span class="bu">int</span>) <span class="op">-&gt;</span> <span class="bu">int</span>:</span>
281<span id="cb3-2"><a href="#cb3-2" aria-hidden="true" tabindex="-1"></a>    a <span class="op">=</span> <span class="bu">abs</span>(a)</span>
282<span id="cb3-3"><a href="#cb3-3" aria-hidden="true" tabindex="-1"></a>    b <span class="op">=</span> <span class="bu">abs</span>(b)</span>
283<span id="cb3-4"><a href="#cb3-4" aria-hidden="true" tabindex="-1"></a>    k <span class="op">=</span> ctz(a <span class="op">|</span> b) <span class="co"># k = min(ctz(a), ctz(b))</span></span>
284<span id="cb3-5"><a href="#cb3-5" aria-hidden="true" tabindex="-1"></a></span>
285<span id="cb3-6"><a href="#cb3-6" aria-hidden="true" tabindex="-1"></a>    <span class="co"># ensure b &gt;&gt; k is odd (if possible)</span></span>
286<span id="cb3-7"><a href="#cb3-7" aria-hidden="true" tabindex="-1"></a>    <span class="cf">if</span> (b <span class="op">&amp;</span> (<span class="dv">1</span> <span class="op">&lt;&lt;</span> k)) <span class="op">==</span> <span class="dv">0</span>:</span>
287<span id="cb3-8"><a href="#cb3-8" aria-hidden="true" tabindex="-1"></a>        a, b <span class="op">=</span> b, a</span>
288<span id="cb3-9"><a href="#cb3-9" aria-hidden="true" tabindex="-1"></a></span>
289<span id="cb3-10"><a href="#cb3-10" aria-hidden="true" tabindex="-1"></a>    <span class="cf">while</span> a <span class="op">!=</span> <span class="dv">0</span>:</span>
290<span id="cb3-11"><a href="#cb3-11" aria-hidden="true" tabindex="-1"></a>        a <span class="op">&gt;&gt;=</span> ctz(a) <span class="op">-</span> k</span>
291<span id="cb3-12"><a href="#cb3-12" aria-hidden="true" tabindex="-1"></a>
291        <span class="cf">if</span> a <span class="op">&lt;</span> b:</span>
292<span id="cb3-13"><a href="#cb3-13" aria-hidden="true" tabindex="-1"></a>            a, b <span class="op">=</span> b, a</span>
293<span id="cb3-14"><a href="#cb3-14" aria-hidden="true" tabindex="-1"></a>        a <span class="op">-=</span> b</span>
294<span id="cb3-15"><a href="#cb3-15" aria-hidden="true" tabindex="-1"></a>    <span class="cf">return</span> b</span></code></pre></div>
295<div id="gcd-demo" class="gcd-demo" data-gcd-demo="">
296<span class="gcd-run-label" data-role="run-label"
297aria-live="polite"></span>
298<div class="gcd-svg-host" data-role="svg-host">
299
300</div>
301<div class="gcd-controls">
302<button type="button" data-action="reset" aria-label="Reset" title="Reset">
303reset
304</button>
305</div>
306</div>
307<script type="module" src="./gcd.js"></script>
307
308<h2 id="code">Code</h2>
309<p>The initialisation portion ensures that we end up with
310<code>L0 = -a</code>, <code>L1 = b</code>, <code>L3 = k-31</code>, with
311<code>a</code> and <code>b</code> positive, and
312<code>b &gt;&gt; k</code> odd (if possible).</p>
313<div class="sourceCode" id="cb4"><pre
314class="sourceCode asm"><code class="sourceCode fasm"><span id="cb4-1"><a href="#cb4-1" aria-hidden="true" tabindex="-1"></a><span class="co">; assume constant register L9 = 0</span></span>
315<span id="cb4-2"><a href="#cb4-2" aria-hidden="true" tabindex="-1"></a>sfpmov   L2<span class="op">,</span>L0<span class="op">,</span><span class="dv">0</span>           <span class="co">; c = a</span></span>
316<span id="cb4-3"><a href="#cb4-3" aria-hidden="true" tabindex="-1"></a>sfpor    L2<span class="op">,</span>L1             <span class="co">; c |= b</span></span>
317<span id="cb4-4"><a href="#cb4-4" aria-hidden="true" tabindex="-1"></a></span>
318<span id="cb4-5"><a href="#cb4-5" aria-hidden="true" tabindex="-1"></a>sfpmov   L3<span class="op">,</span>L2<span class="op">,</span><span class="dv">0</span>           <span class="co">; L3 = c</span></span>
319<span id="cb4-6"><a href="#cb4-6" aria-hidden="true" tabindex="-1"></a>sfpiadd  L3<span class="op">,</span>L9<span class="op">,</span><span class="bn">0x000</span><span class="op">,</span><span class="dv">6</span>     <span class="co">; L3 = -L3</span></span>
320<span id="cb4-7"><a href="#cb4-7" aria-hidden="true" tabindex="-1"></a>sfpand   L3<span class="op">,</span>L2             <span class="co">; L3 &amp;= c (isolate lsb)</span></span>
321<span id="cb4-8"><a href="#cb4-8" aria-hidden="true" tabindex="-1"></a>sfplz    L3<span class="op">,</span>L3<span class="op">,</span><span class="dv">0</span>           <span class="co">; L3 = clz(L3) = 31-k</span></span>
322<span id="cb4-9"><a href="#cb4-9" aria-hidden="true" tabindex="-1"></a></span>
323<span id="cb4-10"><a href="#cb4-10" aria-hidden="true" tabindex="-1"></a><span class="co">; ensure that b is odd if possible: if k-th bit is zero, then swap with a.</span></span>
324<span id="cb4-11"><a href="#cb4-11" aria-hidden="true" tabindex="-1"></a><span class="co">; left-shifting b by 31-k converts its k-th bit to the sign bit.</span></span>
325<span id="cb4-12"><a href="#cb4-12" aria-hidden="true" tabindex="-1"></a>sfpshft2 L2<span class="op">,</span>L3<span class="op">,</span>L1<span class="op">,</span><span class="dv">5</span>        <span class="co">; c = b &lt;&lt; (31-k)</span></span>
326<span id="cb4-13"><a href="#cb4-13" aria-hidden="true" tabindex="-1"></a>sfpsetcc L2<span class="op">,</span><span class="dv">0</span><span class="op">,</span><span class="dv">6</span>            <span class="co">; if c == 0 then b &gt;&gt; k is even</span></span>
327<span id="cb4-14"><a href="#cb4-14" aria-hidden="true" tabindex="-1"></a>sfpswap  L1<span class="op">,</span>L0<span class="op">,</span><span class="dv">0</span>           <span class="co">; swap(a, b)</span></span>
328<span id="cb4-15"><a href="#cb4-15" aria-hidden="true" tabindex="-1"></a>sfpencc  <span class="dv">0</span><span class="op">,</span><span class="dv">0</span><span class="op">,</span><span class="dv">0</span><span class="op">,</span><span class="dv">0</span></span>
329<span id="cb4-16"><a href="#cb4-16" aria-hidden="true" tabindex="-1"></a>sfpabs   L0<span class="op">,</span>L0<span class="op">,</span><span class="dv">0</span>           <span class="co">; a = abs(a)</span></span>
330<span id="cb4-17"><a href="#cb4-17" aria-hidden="true" tabindex="-1"></a>sfpabs   L1<span class="op">,</span>L1<span class="op">,</span><span class="dv">0</span>           <span class="co">; b = abs(b)</span></span>
331<span id="cb4-18"><a href="#cb4-18" aria-hidden="true" tabindex="-1"></a></span>
332<span id="cb4-19"><a href="#cb4-19" aria-hidden="true" tabindex="-1"></a>sfpiadd  L0<span class="op">,</span>L9<span class="op">,</span><span class="dv">6</span>           <span class="co">; a = -a</span></span>
333<span id="cb4-20"><a href="#cb4-20" aria-hidden="true" tabindex="-1"></a>sfpiadd  L3<span class="op">,</span>L9<span class="op">,</span><span class="dv">6</span>
333           <span class="co">; L3 = k-31</span></span></code></pre></div>
334<p>The inner loop consists of the following 7 instructions, consuming
335<strong>8 cycles</strong> per iteration (due to <a
336href="https://github.com/tenstorrent/tt-isa-documentation/blob/main/WormholeB0/TensixTile/TensixCoprocessor/SFPSWAP.md"><code>SFPSWAP</code></a>
337taking two cycles).</p>
338<div class="sourceCode" id="cb5"><pre
339class="sourceCode asm"><code class="sourceCode fasm"><span id="cb5-1"><a href="#cb5-1" aria-hidden="true" tabindex="-1"></a><span class="co">; L0 = -a, L1 = b, L3 = k-31</span></span>
340<span id="cb5-2"><a href="#cb5-2" aria-hidden="true" tabindex="-1"></a>sfpabs   L2<span class="op">,</span>L0<span class="op">,</span><span class="dv">0</span>           <span class="co">; a = abs(-a)</span></span>
341<span id="cb5-3"><a href="#cb5-3" aria-hidden="true" tabindex="-1"></a>sfpand   L0<span class="op">,</span>L2             <span class="co">; a &amp; -a</span></span>
342<span id="cb5-4"><a href="#cb5-4" aria-hidden="true" tabindex="-1"></a>sfplz    L0<span class="op">,</span>L0<span class="op">,</span><span class="dv">2</span>           <span class="co">; clz(a &amp; -a); disable lanes where a=0</span></span>
343<span id="cb5-5"><a href="#cb5-5" aria-hidden="true" tabindex="-1"></a>sfpiadd  L0<span class="op">,</span>L3<span class="op">,</span><span class="bn">0x000</span><span class="op">,</span><span class="dv">4</span>     <span class="co">; -(ctz(a) - k) = clz(a &amp; -a) + k - 31</span></span>
344<span id="cb5-6"><a href="#cb5-6" aria-hidden="true" tabindex="-1"></a>sfpshft2 L0<span class="op">,</span>L0<span class="op">,</span>L2<span class="op">,</span><span class="dv">5</span>        <span class="co">; a &gt;&gt;= (ctz(a) - k) &amp; 31</span></span>
345<span id="cb5-7"><a href="#cb5-7" aria-hidden="true" tabindex="-1"></a>sfpswap  L1<span class="op">,</span>L0<span class="op">,</span><span class="dv">1</span>           <span class="co">; ensure b &lt;= a</span></span>
346<span id="cb5-8"><a href="#cb5-8" aria-hidden="true" tabindex="-1"></a>sfpiadd  L0<span class="op">,</span>L1<span class="op">,</span><span class="bn">0x000</span><span class="op">,</span><span class="dv">6</span>     <span class="co">; -a = b - a (kept in negated form)</span></span></code></pre></div>
347<p>The worst case for 31-bit integers is 31 iterations of the inner
348loop; however, we can skip the final iteration as it only affects
349<code>a</code>, and we can also skip the final instruction of the 30th
350iteration as it only affects <code>a</code> (but we need to consume one
351additional cycle to reset <code>LaneFlags</code> via <a
352href="https://github.com/tenstorrent/tt-isa-documentation/blob/main/WormholeB0/TensixTile/TensixCoprocessor/SFPENCC.md"><code>SFPENCC</code></a>).</p>
353<p>This gives a total cycle count of
354<code>15 + 30 * 8 - 1 + 1 = 255</code>.</p>
355<h2 id="acknowledgements">Acknowledgements</h2>
356<ul>
357<li>Thanks to <a href="https://corsix.org"><span class="citation"
358data-cites="corsix">@corsix</span></a> for ingenious suggestions on
359attempting to add an early-exit termination condition via
360<code>NaN</code> sticky bits, which unfortunately didn’t work reliably
361due to hardware bugs.</li>
362<li>Thanks to <a href="https://tenstorrent.com">Tenstorrent</a> for
363sponsoring this work.</li>
364</ul>
365<footer style="text-align:center; margin-top:3em; font-size:0.9em">
366  <p>
367    <a href="/">jasondavies.com</a> |
368    <a href="https://x.com/jasondavies">@jasondavies</a>
369  </p>
370</footer>
371</body>
372</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.