docs/kmeans.html · Ean/cpp-taskflow

代码拉取完成,页面将自动刷新

扫描微信二维码支付

取消

支付完成

richgiteeai

Watch

不关注关注所有动态仅关注版本发行动态关注但不提醒动态

1 Star 0 Fork 37

Ean/cpp-taskflow

forked from Gitee 极速下载/cpp-taskflow

代码 Wiki 统计流水线

服务

加入 Gitee

与超过 1400万开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)

免费加入

已有帐号? 立即登录

文件

master

分支 (5)

标签 (17)

管理

master

dev

dev-defer-new

dev-defer

cpp14

v3.6.0

v3.5.0

v3.4.0

v3.3.0

v3.2.0

v3.1.0

v3.0.0

v2.7.0

v2.6.0

v2.5.0

2.5.0

v2.4.0

v2.3.1

v2.3.0

v2.2.0

v2.1.0

v2.0.0

克隆/下载

HTTPS SSH SVN SVN+SSH 下载ZIP

提示

下载代码请复制以下命令到终端执行

为确保你提交的代码身份被 Gitee 正确识别,请执行以下命令完成配置

git config --global user.name userName 
git config --global user.email userEmail

初次使用 SSH 协议进行代码克隆、推送等操作时,需按下述提示完成 SSH 配置

1 生成 RSA 密钥

2 获取 RSA 公钥内容,并配置到 SSH公钥中

在 Gitee 上使用 SVN,请访问使用指南

使用 HTTPS 协议时,命令行会出现如下账号密码验证步骤。基于安全考虑,Gitee 建议配置并使用私人令牌替代登录密码进行克隆、推送等操作

Username for 'https://gitee.com': userName

Password for 'https://userName@gitee.com': # 私人令牌

分支 5

标签 17

cpp-taskflow

docs

kmeans.html

kmeans.html 63.08 KB

<!DOCTYPE html>
<html lang="en">
<head>
 <meta charset="UTF-8" />
 <title>Learning from Examples &raquo; k-means Clustering | Taskflow QuickStart</title>
 <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Source+Sans+Pro:400,400i,600,600i%7CSource+Code+Pro:400,400i,600" />
 <link rel="stylesheet" href="m-dark+documentation.compiled.css" />
 <link rel="icon" href="favicon.ico" type="image/vnd.microsoft.icon" />
 <meta name="viewport" content="width=device-width, initial-scale=1.0" />
 <meta name="theme-color" content="#22272e" />
</head>
<body>
<header><nav id="navigation">
 <div class="m-container">
 <div class="m-row">
 
 <a href="https://taskflow.github.io"><img src="taskflow_logo.png" alt="" />Taskflow</a> | <a href="index.html" class="m-thin">QuickStart</a>
 
 <div class="m-col-t-4 m-hide-m m-text-right m-nopadr">
 <a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
 <path id="m-doc-search-icon-path" d="m6 0c-3.31 0-6 2.69-6 6 0 3.31 2.69 6 6 6 1.49 0 2.85-0.541 3.89-1.44-0.0164 0.338 0.147 0.759 0.5 1.15l3.22 3.79c0.552 0.614 1.45 0.665 2 0.115 0.55-0.55 0.499-1.45-0.115-2l-3.79-3.22c-0.392-0.353-0.812-0.515-1.15-0.5 0.895-1.05 1.44-2.41 1.44-3.89 0-3.31-2.69-6-6-6zm0 1.56a4.44 4.44 0 0 1 4.44 4.44 4.44 4.44 0 0 1-4.44 4.44 4.44 4.44 0 0 1-4.44-4.44 4.44 4.44 0 0 1 4.44-4.44z"/>
 </svg></a>
 <a id="m-navbar-show" href="#navigation" title="Show navigation"></a>
 <a id="m-navbar-hide" href="#" title="Hide navigation"></a>
 </div>
 <div id="m-navbar-collapse" class="m-col-t-12 m-show-m m-col-m-none m-right-m">
 <div class="m-row">
 <ol class="m-col-t-6 m-col-m-none">
 <li><a href="pages.html">Handbook</a></li>
 <li><a href="namespaces.html">Namespaces</a></li>
 </ol>
 <ol class="m-col-t-6 m-col-m-none" start="3">
 <li><a href="annotated.html">Classes</a></li>
 <li><a href="files.html">Files</a></li>
 <li class="m-show-m"><a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
 <use href="#m-doc-search-icon-path" />
 </svg></a></li>
 </ol>
 </div>
 </div>
 </div>
 </div>
</nav></header>
<main><article>
 <div class="m-container m-container-inflatable">
 <div class="m-row">
 <div class="m-col-l-10 m-push-l-1">
 <h1>
 <a href="Examples.html">Learning from Examples</a> &raquo;
 k-means Clustering
 </h1>
 <nav class="m-block m-default">
 <h3>Contents</h3>
 <ul>
 <li><a href="#KMeansProblemFormulation">Problem Formulation</a></li>
 <li><a href="#ParallelKMeansUsingCPUs">Parallel k-means using CPUs</a></li>
 <li><a href="#KMeansBenchmarking">Benchmarking</a></li>
 </ul>
 </nav>
We study a fundamental clustering problem in unsupervised learning, k-means clustering. We will begin by discussing the problem formulation and then learn how to write a parallel k-means algorithm.<section id="KMeansProblemFormulation"><h2><a href="#KMeansProblemFormulation">Problem Formulation</a></h2>k-means clustering uses centroids, k different randomly-initiated points in the data, and assigns every data point to the nearest centroid. After every point has been assigned, the centroid is moved to the average of all of the points assigned to it. We describe the k-means algorithm in the following steps:<ul><li>Step 1: initialize k random centroids</li><li>Step 2: for every data point, find the nearest centroid (L2 distance or other measurements) and assign the point to it</li><li>Step 3: for every centroid, move the centroid to the average of the points assigned to that centroid</li><li>Step 4: go to Step 2 until converged (no more changes in the last few iterations) or maximum iterations reached</li></ul>The algorithm is illustrated as follows:<img class="m-image" src="kmeans_1.png" alt="Image" />A sequential implementation of k-means is described as follows:<pre class="m-code">// sequential implementation of k-means on a CPU
// N: number of points
// K: number of clusters
// M: number of iterations
// px/py: 2D point vector 
void kmeans_seq(
 int N, int K, int M, const std::vector&lt;float&gt;&amp; px, const std::vector&lt;float&gt;&amp; py
) {

std::vector&lt;int&gt; c(K);
 std::vector&lt;float&gt; sx(K), sy(K), mx(K), my(K);

// initial centroids
 std::copy_n(px.begin(), K, mx.begin());
 std::copy_n(py.begin(), K, my.begin());
 
 // k-means iteration
 for(int m=0; m&lt;M; m++) {

// clear the storage
 std::fill_n(sx.begin(), K, 0.0f);
 std::fill_n(sy.begin(), K, 0.0f);
 std::fill_n(c.begin(), K, 0);

// find the best k (cluster id) for each point
 for(int i=0; i&lt;N; ++i) {
 float x = px[i];
 float y = py[i];
 float best_d = std::numeric_limits&lt;float&gt;::max();
 int best_k = 0;
 for (int k = 0; k &lt; K; ++k) {
 const float d = L2(x, y, mx[k], my[k]);
 if (d &lt; best_d) {
 best_d = d;
 best_k = k;
 }
 }
 sx[best_k] += x;
 sy[best_k] += y;
 c [best_k] += 1;
 }

// update the centroid
 for(int k=0; k&lt;K; k++) {
 const int count = max(1, c[k]); // turn 0/0 to 0/1
 mx[k] = sx[k] / count;
 my[k] = sy[k] / count;
 }
 }

// print the k centroids found
 for(int k=0; k&lt;K; ++k) {
 std::cout &lt;&lt; &quot;centroid &quot; &lt;&lt; k &lt;&lt; &quot;: &quot; &lt;&lt; std::setw(10) &lt;&lt; mx[k] &lt;&lt; &#39; &#39;
 &lt;&lt; std::setw(10) &lt;&lt; my[k] &lt;&lt; &#39;\n&#39;;
 }
}</pre></section><section id="ParallelKMeansUsingCPUs"><h2><a href="#ParallelKMeansUsingCPUs">Parallel k-means using CPUs</a></h2>The second step of k-means algorithm, assigning every point to the nearest centroid, is highly parallelizable across individual points. We can create a parallel-for task to run parallel iterations.<pre class="m-code">std::vector&lt;int&gt; best_ks(N); // nearest centroid of each point

unsigned P = 12; // 12 partitioned tasks

// update cluster
taskflow.for_each_index(0, N, 1, [&amp;](int i){
 float x = px[i];
 float y = py[i];
 float best_d = std::numeric_limits&lt;float&gt;::max();
 int best_k = 0;
 for (int k = 0; k &lt; K; ++k) {
 const float d = L2(x, y, mx[k], my[k]);
 if (d &lt; best_d) {
 best_d = d;
 best_k = k;
 }
 }
 best_ks[i] = best_k;
});</pre>The third step of moving every centroid to the average of points is also parallelizable across individual centroids. However, since k is typically not large, one task of doing this update is sufficient.<pre class="m-code">taskflow.emplace([&amp;](){
 // sum of points
 for(int i=0; i&lt;N; i++) {
 sx[best_ks[i]] += px[i];
 sy[best_ks[i]] += py[i];
 c [best_ks[i]] += 1;
 }
 
 // average of points
 for(int k=0; k&lt;K; ++k) {
 auto count = max(1, c[k]); // turn 0/0 to 0/1
 mx[k] = sx[k] / count;
 my[k] = sy[k] / count;
 }
});</pre>To describe <code>M</code> iterations, we create a condition task that loops the second step of the algorithm by <code>M</code> times. The return value of zero goes to the first successor which we will connect to the task of the second step later; otherwise, k-means completes.<pre class="m-code">taskflow.emplace([m=0, M]() mutable {
 return (m++ &lt; M) ? 0 : 1;
});</pre>The entire code of CPU-parallel k-means is shown below. Here we use an additional storage, <code>best_ks</code>, to record the nearest centroid of a point at an iteration.<pre class="m-code">// N: number of points
// K: number of clusters
// M: number of iterations
// px/py: 2D point vector 
void kmeans_par(
 int N, int K, int M, cconst std::vector&lt;float&gt;&amp; px, const std::vector&lt;float&gt;&amp; py
) {

unsigned P = 12; // 12 partitions of the parallel-for graph

tf::Executor executor;
 tf::Taskflow taskflow(&quot;K-Means&quot;);

std::vector&lt;int&gt; c(K), best_ks(N);
 std::vector&lt;float&gt; sx(K), sy(K), mx(K), my(K);

// initial centroids
 tf::Task init = taskflow.emplace([&amp;](){
 for(int i=0; i&lt;K; ++i) {
 mx[i] = px[i];
 my[i] = py[i];
 }
 }).name(&quot;init&quot;);

// clear the storage
 tf::Task clean_up = taskflow.emplace([&amp;](){
 for(int k=0; k&lt;K; ++k) {
 sx[k] = 0.0f;
 sy[k] = 0.0f;
 c [k] = 0;
 }
 }).name(&quot;clean_up&quot;);

// update cluster
 tf::Task pf = taskflow.for_each_index(0, N, 1, [&amp;](int i){
 float x = px[i];
 float y = py[i];
 float best_d = std::numeric_limits&lt;float&gt;::max();
 int best_k = 0;
 for (int k = 0; k &lt; K; ++k) {
 const float d = L2(x, y, mx[k], my[k]);
 if (d &lt; best_d) {
 best_d = d;
 best_k = k;
 }
 }
 best_ks[i] = best_k;
 }).name(&quot;parallel-for&quot;);

tf::Task update_cluster = taskflow.emplace([&amp;](){
 for(int i=0; i&lt;N; i++) {
 sx[best_ks[i]] += px[i];
 sy[best_ks[i]] += py[i];
 c [best_ks[i]] += 1;
 }

for(int k=0; k&lt;K; ++k) {
 auto count = max(1, c[k]); // turn 0/0 to 0/1
 mx[k] = sx[k] / count;
 my[k] = sy[k] / count;
 }
 }).name(&quot;update_cluster&quot;);
 
 // convergence check
 tf::Task condition = taskflow.emplace([m=0, M]() mutable {
 return (m++ &lt; M) ? 0 : 1;
 }).name(&quot;converged?&quot;);

init.precede(clean_up);

clean_up.precede(pf);
 pf.precede(update_cluster);

condition.precede(clean_up)
 .succeed(update_cluster);

executor.run(taskflow).wait();
}</pre>The taskflow consists of two parts, a <code>clean_up</code> task and a parallel-for graph. The former cleans up the storage <code>sx</code>, <code>sy</code>, and <code>c</code> that are used to average points for new centroids, and the later parallelizes the searching for nearest centroids across individual points using 12 tasks (may vary depending on the machine). If the iteration count is smaller than <code>M</code>, the condition task returns 0 to let the execution path go back to <code>clean_up</code>. Otherwise, it returns 1 to stop (i.e., no successor tasks at index 1). The taskflow graph is illustrated below:<div class="m-graph"><svg style="width: 65.500rem; height: 74.300rem;" viewBox="0.00 0.00 655.42 743.00">
<g transform="scale(1 1) rotate(0) translate(4 739)">
<title>Taskflow</title>
<g class="m-cluster">
<title>cluster_p0x1dcb6e0</title>
<polygon points="8,-8 8,-727 241.4564,-727 241.4564,-8 8,-8"/>
<text text-anchor="middle" x="124.7282" y="-715" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">Subflow: parallel&#45;for</text>
</g>
<g class="m-node m-flat">
<title>p0x1dcb4c0</title>
<ellipse cx="473.0106" cy="-421" rx="27" ry="18"/>
<text text-anchor="middle" x="473.0106" y="-418.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">init</text>
</g>
<g class="m-node m-flat">
<title>p0x1dcb5d0</title>
<ellipse cx="612.1025" cy="-375" rx="35.1405" ry="18"/>
<text text-anchor="middle" x="612.1025" y="-372.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">clean_up</text>
</g>
<g class="m-edge">
<title>p0x1dcb4c0&#45;&gt;p0x1dcb5d0</title>
<path d="M497.2385,-412.9874C518.0347,-406.1098 548.4065,-396.0653 572.6966,-388.0322"/>
<polygon points="573.9539,-391.3029 582.3491,-384.8399 571.7559,-384.6569 573.9539,-391.3029"/>
</g>
<g class="m-node m-flat">
<title>p0x1dcb6e0</title>
<ellipse cx="191.6614" cy="-358" rx="41.5911" ry="18"/>
<text text-anchor="middle" x="191.6614" y="-355.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">parallel&#45;for</text>
</g>
<g class="m-edge">
<title>p0x1dcb5d0&#45;&gt;p0x1dcb6e0</title>
<path d="M576.7397,-373.5701C502.5679,-370.5711 330.439,-363.6113 243.6594,-360.1025"/>
<polygon points="243.6452,-356.5991 233.512,-359.6922 243.3624,-363.5934 243.6452,-356.5991"/>
</g>
<g class="m-node m-flat">
<title>p0x1dcb7f0</title>
<ellipse cx="322.8474" cy="-329" rx="52.2822" ry="18"/>
<text text-anchor="middle" x="322.8474" y="-326.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">update_cluster</text>
</g>
<g class="m-edge">
<title>p0x1dcb6e0&#45;&gt;p0x1dcb7f0</title>
<path d="M228.9031,-349.7673C241.2173,-347.0452 255.1824,-343.958 268.5086,-341.0122"/>
<polygon points="269.5279,-344.3714 278.5367,-338.7953 268.0169,-337.5364 269.5279,-344.3714"/>
</g>
<g class="m-node">
<title>p0x1dcb900</title>
<polygon points="473.0106,-347 412.4654,-329 473.0106,-311 533.5557,-329 473.0106,-347"/>
<text text-anchor="middle" x="473.0106" y="-326.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">converged?</text>
</g>
<g class="m-edge">
<title>p0x1dcb7f0&#45;&gt;p0x1dcb900</title>
<path d="M375.3672,-329C384.0316,-329 393.1379,-329 402.1623,-329"/>
<polygon points="402.2886,-332.5001 412.2886,-329 402.2885,-325.5001 402.2886,-332.5001"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000b50</title>
<ellipse cx="45.4331" cy="-682" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-679.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_0</text>
</g>
<g class="m-edge">
<title>p0x7fd610000b50&#45;&gt;p0x1dcb6e0</title>
<path d="M62.9675,-668.3116C67.2604,-664.355 71.5644,-659.7985 74.8663,-655 135.9443,-566.2373 171.6244,-440.9464 185.2481,-385.8438"/>
<polygon points="188.6574,-386.6358 187.6082,-376.093 181.8539,-384.989 188.6574,-386.6358"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000c60</title>
<ellipse cx="45.4331" cy="-628" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-625.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_1</text>
</g>
<g class="m-edge">
<title>p0x7fd610000c60&#45;&gt;p0x1dcb6e0</title>
<path d="M62.7393,-614.1485C67.034,-610.1931 71.3959,-605.6781 74.8663,-601 127.2191,-530.4291 165.5956,-432.6887 182.3416,-385.5741"/>
<polygon points="185.6745,-386.6462 185.6755,-376.0514 179.0677,-384.3332 185.6745,-386.6462"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000d70</title>
<ellipse cx="45.4331" cy="-574" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-571.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_2</text>
</g>
<g class="m-edge">
<title>p0x7fd610000d70&#45;&gt;p0x1dcb6e0</title>
<path d="M62.4118,-559.8919C66.7091,-555.9385 71.1541,-551.4886 74.8663,-547 118.8306,-493.8406 158.3695,-422.7142 178.2093,-384.6693"/>
<polygon points="181.3415,-386.2319 182.8196,-375.7407 175.1217,-383.0203 181.3415,-386.2319"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000e80</title>
<ellipse cx="45.4331" cy="-520" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-517.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_3</text>
</g>
<g class="m-edge">
<title>p0x7fd610000e80&#45;&gt;p0x1dcb6e0</title>
<path d="M61.943,-505.4716C66.2439,-501.5214 70.8079,-497.1782 74.8663,-493 110.4817,-456.3333 148.6863,-410.8751 171.3596,-383.1744"/>
<polygon points="174.2729,-385.14 177.8775,-375.1772 168.8467,-380.7176 174.2729,-385.14"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000f90</title>
<ellipse cx="45.4331" cy="-466" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-463.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_4</text>
</g>
<g class="m-edge">
<title>p0x7fd610000f90&#45;&gt;p0x1dcb6e0</title>
<path d="M63.6574,-452.5401C88.3249,-434.3214 132.6364,-401.5941 162.1001,-379.8331"/>
<polygon points="164.3936,-382.4903 170.3582,-373.7339 160.2349,-376.8596 164.3936,-382.4903"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100010a0</title>
<ellipse cx="45.4331" cy="-412" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-409.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_5</text>
</g>
<g class="m-edge">
<title>p0x7fd6100010a0&#45;&gt;p0x1dcb6e0</title>
<path d="M69.2527,-403.2038C91.1398,-395.1212 124.0586,-382.9647 150.2479,-373.2934"/>
<polygon points="151.7503,-376.4697 159.9186,-369.7221 149.3254,-369.9031 151.7503,-376.4697"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100011b0</title>
<ellipse cx="45.4331" cy="-358" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-355.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_6</text>
</g>
<g class="m-edge">
<title>p0x7fd6100011b0&#45;&gt;p0x1dcb6e0</title>
<path d="M72.5949,-358C91.3605,-358 116.9179,-358 139.544,-358"/>
<polygon points="139.6986,-361.5001 149.6986,-358 139.6985,-354.5001 139.6986,-361.5001"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100012c0</title>
<ellipse cx="45.4331" cy="-304" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-301.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_7</text>
</g>
<g class="m-edge">
<title>p0x7fd6100012c0&#45;&gt;p0x1dcb6e0</title>
<path d="M69.2527,-312.7962C91.1398,-320.8788 124.0586,-333.0353 150.2479,-342.7066"/>
<polygon points="149.3254,-346.0969 159.9186,-346.2779 151.7503,-339.5303 149.3254,-346.0969"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100013d0</title>
<ellipse cx="45.4331" cy="-250" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-247.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_8</text>
</g>
<g class="m-edge">
<title>p0x7fd6100013d0&#45;&gt;p0x1dcb6e0</title>
<path d="M63.6574,-263.4599C88.3249,-281.6786 132.6364,-314.4059 162.1001,-336.1669"/>
<polygon points="160.2349,-339.1404 170.3582,-342.2661 164.3936,-333.5097 160.2349,-339.1404"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100014e0</title>
<ellipse cx="45.4331" cy="-196" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-193.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_9</text>
</g>
<g class="m-edge">
<title>p0x7fd6100014e0&#45;&gt;p0x1dcb6e0</title>
<path d="M61.943,-210.5284C66.2439,-214.4786 70.8079,-218.8218 74.8663,-223 110.4817,-259.6667 148.6863,-305.1249 171.3596,-332.8256"/>
<polygon points="168.8467,-335.2824 177.8775,-340.8228 174.2729,-330.86 168.8467,-335.2824"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100015f0</title>
<ellipse cx="45.4331" cy="-142" rx="29.3664" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-139.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_10</text>
</g>
<g class="m-edge">
<title>p0x7fd6100015f0&#45;&gt;p0x1dcb6e0</title>
<path d="M63.0266,-156.6762C67.1307,-160.4853 71.3309,-164.7251 74.8663,-169 118.8306,-222.1594 158.3695,-293.2858 178.2093,-331.3307"/>
<polygon points="175.1217,-332.9797 182.8196,-340.2593 181.3415,-329.7681 175.1217,-332.9797"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610001700</title>
<ellipse cx="45.4331" cy="-88" rx="29.3664" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-85.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_11</text>
</g>
<g class="m-edge">
<title>p0x7fd610001700&#45;&gt;p0x1dcb6e0</title>
<path d="M63.3532,-102.4203C67.4474,-106.2372 71.5611,-110.5447 74.8663,-115 127.2191,-185.5709 165.5956,-283.3113 182.3416,-330.4259"/>
<polygon points="179.0677,-331.6668 185.6755,-339.9486 185.6745,-329.3538 179.0677,-331.6668"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610001810</title>
<ellipse cx="45.4331" cy="-34" rx="29.3664" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-31.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_12</text>
</g>
<g class="m-edge">
<title>p0x7fd610001810&#45;&gt;p0x1dcb6e0</title>
<path d="M63.5808,-48.2577C67.6681,-52.0795 71.7217,-56.43 74.8663,-61 135.9443,-149.7627 171.6244,-275.0536 185.2481,-330.1562"/>
<polygon points="181.8539,-331.011 187.6082,-339.907 188.6574,-329.3642 181.8539,-331.011"/>
</g>
<g class="m-edge">
<title>p0x1dcb900&#45;&gt;p0x1dcb5d0</title>
<path stroke-dasharray="5,2" d="M509.366,-336.2239C524.8076,-339.7212 542.8801,-344.3877 558.7827,-350 565.0464,-352.2106 571.565,-354.9093 577.8057,-357.706"/>
<polygon points="576.7638,-361.0815 587.3071,-362.1255 579.7161,-354.7345 576.7638,-361.0815"/>
<text text-anchor="middle" x="555.2827" y="-353" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">0</text>
</g>
</g>
</svg>
</div>The scheduler starts with <code>init</code>, moves on to <code>clean_up</code>, and then enters the parallel-for task <code>paralle-for</code> that spawns a subflow of 12 workers to perform parallel iterations. When <code>parallel-for</code> completes, it updates the cluster centroids and checks if they have converged through a condition task. If not, the condition task informs the scheduler to go back to <code>clean_up</code> and then <code>parallel-for</code>; otherwise, it returns a nominal index to stop the scheduler.</section><section id="KMeansBenchmarking"><h2><a href="#KMeansBenchmarking">Benchmarking</a></h2>Based on the discussion above, we compare the runtime of computing various k-means problem sizes between a sequential CPU and parallel CPUs on a machine of 12 Intel i7-8700 CPUs at 3.2 GHz.<table class="m-table"><thead><tr><th>N</th><th>K</th><th>M</th><th>CPU Sequential</th><th>CPU Parallel</th></tr></thead><tbody><tr><td>10</td><td>5</td><td>10</td><td>0.14 ms</td><td>77 ms</td></tr><tr><td>100</td><td>10</td><td>100</td><td>0.56 ms</td><td>86 ms</td></tr><tr><td>1000</td><td>10</td><td>1000</td><td>10 ms</td><td>98 ms</td></tr><tr><td>10000</td><td>10</td><td>10000</td><td>1006 ms</td><td>713 ms</td></tr><tr><td>100000</td><td>10</td><td>100000</td><td>102483 ms</td><td>49966 ms</td></tr></tbody></table>When the number of points is larger than 10K, the parallel CPU implementation starts to outperform the sequential CPU implementation.</section>
 </div>
 </div>
 </div>
</article></main>
<div class="m-doc-search" id="search">
 <a href="#!" onclick="return hideSearch()"></a>
 <div class="m-container">
 <div class="m-row">
 <div class="m-col-m-8 m-push-m-2">
 <div class="m-doc-search-header m-text m-small">
 <div>Tab / T to search, Esc to close</div>
 <div id="search-symbolcount">&hellip;</div>
 </div>
 <div class="m-doc-search-content">
 <form>
 <input type="search" name="q" id="search-input" placeholder="Loading &hellip;" disabled="disabled" autofocus="autofocus" autocomplete="off" spellcheck="false" />
 </form>
 <noscript class="m-text m-danger m-text-center">Unlike everything else in the docs, the search functionality requires JavaScript.</noscript>
 <div id="search-help" class="m-text m-dim m-text-center">
 Search for symbols, directories, files, pages or
 modules. You can omit any prefix from the symbol or file path; adding a
 <code>:</code> or <code>/</code> suffix lists all members of given symbol or
 directory.
 Use &darr;
 / &uarr; to navigate through the list,
 Enter to go.
 Tab autocompletes common prefix, you can
 copy a link to the result using ⌘
 L while ⌘
 M produces a Markdown link.
 </div>
 <div id="search-notfound" class="m-text m-warning m-text-center">Sorry, nothing was found.</div>
 <ul id="search-results"></ul>
 </div>
 </div>
 </div>
 </div>
</div>
<script src="search-v2.js"></script>
<script src="searchdata-v2.js" async="async"></script>
<footer><nav>
 <div class="m-container">
 <div class="m-row">
 <div class="m-col-l-10 m-push-l-1">
 Taskflow handbook is part of the <a href="https://taskflow.github.io">Taskflow project</a>, copyright © <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>, 2018&ndash;2023. Generated by <a href="https://doxygen.org/">Doxygen</a> 1.8.14 and <a href="https://mcss.mosra.cz/">m.css</a>.
 </div>
 </div>
 </div>
</nav></footer>
</body>
</html>

一键复制编辑原始数据按行查看历史

twhuang 提交于 2023年05月10日 03:18 +08:00 . fixed old async behavior in documentation

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468

<!DOCTYPE html>
<html lang="en">
<head>
 <meta charset="UTF-8" />
 <title>Learning from Examples &raquo; k-means Clustering | Taskflow QuickStart</title>
 <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Source+Sans+Pro:400,400i,600,600i%7CSource+Code+Pro:400,400i,600" />
 <link rel="stylesheet" href="m-dark+documentation.compiled.css" />
 <link rel="icon" href="favicon.ico" type="image/vnd.microsoft.icon" />
 <meta name="viewport" content="width=device-width, initial-scale=1.0" />
 <meta name="theme-color" content="#22272e" />
</head>
<body>
<header><nav id="navigation">
 <div class="m-container">
 <div class="m-row">
 <span id="m-navbar-brand" class="m-col-t-8 m-col-m-none m-left-m">
 <a href="https://taskflow.github.io"><img src="taskflow_logo.png" alt="" />Taskflow</a> <span class="m-breadcrumb">|</span> <a href="index.html" class="m-thin">QuickStart</a>
 </span>
 <div class="m-col-t-4 m-hide-m m-text-right m-nopadr">
 <a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
 <path id="m-doc-search-icon-path" d="m6 0c-3.31 0-6 2.69-6 6 0 3.31 2.69 6 6 6 1.49 0 2.85-0.541 3.89-1.44-0.0164 0.338 0.147 0.759 0.5 1.15l3.22 3.79c0.552 0.614 1.45 0.665 2 0.115 0.55-0.55 0.499-1.45-0.115-2l-3.79-3.22c-0.392-0.353-0.812-0.515-1.15-0.5 0.895-1.05 1.44-2.41 1.44-3.89 0-3.31-2.69-6-6-6zm0 1.56a4.44 4.44 0 0 1 4.44 4.44 4.44 4.44 0 0 1-4.44 4.44 4.44 4.44 0 0 1-4.44-4.44 4.44 4.44 0 0 1 4.44-4.44z"/>
 </svg></a>
 <a id="m-navbar-show" href="#navigation" title="Show navigation"></a>
 <a id="m-navbar-hide" href="#" title="Hide navigation"></a>
 </div>
 <div id="m-navbar-collapse" class="m-col-t-12 m-show-m m-col-m-none m-right-m">
 <div class="m-row">
 <ol class="m-col-t-6 m-col-m-none">
 <li><a href="pages.html">Handbook</a></li>
 <li><a href="namespaces.html">Namespaces</a></li>
 </ol>
 <ol class="m-col-t-6 m-col-m-none" start="3">
 <li><a href="annotated.html">Classes</a></li>
 <li><a href="files.html">Files</a></li>
 <li class="m-show-m"><a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
 <use href="#m-doc-search-icon-path" />
 </svg></a></li>
 </ol>
 </div>
 </div>
 </div>
 </div>
</nav></header>
<main><article>
 <div class="m-container m-container-inflatable">
 <div class="m-row">
 <div class="m-col-l-10 m-push-l-1">
 <h1>
 <span class="m-breadcrumb"><a href="Examples.html">Learning from Examples</a> &raquo;</span>
 k-means Clustering
 </h1>
 <nav class="m-block m-default">
 <h3>Contents</h3>
 <ul>
 <li><a href="#KMeansProblemFormulation">Problem Formulation</a></li>
 <li><a href="#ParallelKMeansUsingCPUs">Parallel k-means using CPUs</a></li>
 <li><a href="#KMeansBenchmarking">Benchmarking</a></li>
 </ul>
 </nav>
<p>We study a fundamental clustering problem in unsupervised learning, <em>k-means clustering</em>. We will begin by discussing the problem formulation and then learn how to write a parallel k-means algorithm.</p><section id="KMeansProblemFormulation"><h2><a href="#KMeansProblemFormulation">Problem Formulation</a></h2><p>k-means clustering uses <em>centroids</em>, k different randomly-initiated points in the data, and assigns every data point to the nearest centroid. After every point has been assigned, the centroid is moved to the average of all of the points assigned to it. We describe the k-means algorithm in the following steps:</p><ul><li>Step 1: initialize k random centroids</li><li>Step 2: for every data point, find the nearest centroid (L2 distance or other measurements) and assign the point to it</li><li>Step 3: for every centroid, move the centroid to the average of the points assigned to that centroid</li><li>Step 4: go to Step 2 until converged (no more changes in the last few iterations) or maximum iterations reached</li></ul><p>The algorithm is illustrated as follows:</p><img class="m-image" src="kmeans_1.png" alt="Image" /><p>A sequential implementation of k-means is described as follows:</p><pre class="m-code"><span class="c1">// sequential implementation of k-means on a CPU</span>
<span class="c1">// N: number of points</span>
<span class="c1">// K: number of clusters</span>
<span class="c1">// M: number of iterations</span>
<span class="c1">// px/py: 2D point vector </span>
<span class="kt">void</span><span class="w"> </span><span class="nf">kmeans_seq</span><span class="p">(</span><span class="w"></span>
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">N</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">K</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">M</span><span class="p">,</span><span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;&amp;</span><span class="w"> </span><span class="n">px</span><span class="p">,</span><span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;&amp;</span><span class="w"> </span><span class="n">py</span><span class="w"></span>
<span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>

<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">c</span><span class="p">(</span><span class="n">K</span><span class="p">);</span><span class="w"></span>
<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;</span><span class="w"> </span><span class="n">sx</span><span class="p">(</span><span class="n">K</span><span class="p">),</span><span class="w"> </span><span class="n">sy</span><span class="p">(</span><span class="n">K</span><span class="p">),</span><span class="w"> </span><span class="n">mx</span><span class="p">(</span><span class="n">K</span><span class="p">),</span><span class="w"> </span><span class="n">my</span><span class="p">(</span><span class="n">K</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="c1">// initial centroids</span>
<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">copy_n</span><span class="p">(</span><span class="n">px</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">K</span><span class="p">,</span><span class="w"> </span><span class="n">mx</span><span class="p">.</span><span class="n">begin</span><span class="p">());</span><span class="w"></span>
<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">copy_n</span><span class="p">(</span><span class="n">py</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">K</span><span class="p">,</span><span class="w"> </span><span class="n">my</span><span class="p">.</span><span class="n">begin</span><span class="p">());</span><span class="w"></span>
<span class="w"> </span>
<span class="w"> </span><span class="c1">// k-means iteration</span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">m</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">m</span><span class="o">&lt;</span><span class="n">M</span><span class="p">;</span><span class="w"> </span><span class="n">m</span><span class="o">++</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>

<span class="w"> </span><span class="c1">// clear the storage</span>
<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">fill_n</span><span class="p">(</span><span class="n">sx</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">K</span><span class="p">,</span><span class="w"> </span><span class="mf">0.0f</span><span class="p">);</span><span class="w"></span>
<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">fill_n</span><span class="p">(</span><span class="n">sy</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">K</span><span class="p">,</span><span class="w"> </span><span class="mf">0.0f</span><span class="p">);</span><span class="w"></span>
<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">fill_n</span><span class="p">(</span><span class="n">c</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">K</span><span class="p">,</span><span class="w"> </span><span class="mi">0</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="c1">// find the best k (cluster id) for each point</span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">i</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">px</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">py</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">best_d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">numeric_limits</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;::</span><span class="n">max</span><span class="p">();</span><span class="w"></span>
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">best_k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">k</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">L2</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">y</span><span class="p">,</span><span class="w"> </span><span class="n">mx</span><span class="p">[</span><span class="n">k</span><span class="p">],</span><span class="w"> </span><span class="n">my</span><span class="p">[</span><span class="n">k</span><span class="p">]);</span><span class="w"></span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">d</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">best_d</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">best_d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">d</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">best_k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">k</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="n">sx</span><span class="p">[</span><span class="n">best_k</span><span class="p">]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="n">x</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">sy</span><span class="p">[</span><span class="n">best_k</span><span class="p">]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="n">y</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">[</span><span class="n">best_k</span><span class="p">]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>

<span class="w"> </span><span class="c1">// update the centroid</span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="o">&lt;</span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="o">++</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">count</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">max</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">[</span><span class="n">k</span><span class="p">]);</span><span class="w"> </span><span class="c1">// turn 0/0 to 0/1</span>
<span class="w"> </span><span class="n">mx</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">sx</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">count</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">my</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">sy</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">count</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>

<span class="w"> </span><span class="c1">// print the k centroids found</span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="o">&lt;</span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">k</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">cout</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="s">&quot;centroid &quot;</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="s">&quot;: &quot;</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">setw</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="n">mx</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="sc">&#39; &#39;</span><span class="w"></span>
<span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">setw</span><span class="p">(</span><span class="mi">10</span><span class="p">)</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="n">my</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">&lt;&lt;</span><span class="w"> </span><span class="sc">&#39;\n&#39;</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="p">}</span><span class="w"></span></pre></section><section id="ParallelKMeansUsingCPUs"><h2><a href="#ParallelKMeansUsingCPUs">Parallel k-means using CPUs</a></h2><p>The second step of k-means algorithm, <em>assigning every point to the nearest centroid</em>, is highly parallelizable across individual points. We can create a <em>parallel-for</em> task to run parallel iterations.</p><pre class="m-code"><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">best_ks</span><span class="p">(</span><span class="n">N</span><span class="p">);</span><span class="w"> </span><span class="c1">// nearest centroid of each point</span>

<span class="kt">unsigned</span><span class="w"> </span><span class="n">P</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">12</span><span class="p">;</span><span class="w"> </span><span class="c1">// 12 partitioned tasks</span>

<span class="c1">// update cluster</span>
<span class="n">taskflow</span><span class="p">.</span><span class="n">for_each_index</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">N</span><span class="p">,</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="p">[</span><span class="o">&amp;</span><span class="p">](</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">){</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">px</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">py</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">best_d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">numeric_limits</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;::</span><span class="n">max</span><span class="p">();</span><span class="w"></span>
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">best_k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">k</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">L2</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">y</span><span class="p">,</span><span class="w"> </span><span class="n">mx</span><span class="p">[</span><span class="n">k</span><span class="p">],</span><span class="w"> </span><span class="n">my</span><span class="p">[</span><span class="n">k</span><span class="p">]);</span><span class="w"></span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">d</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">best_d</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">best_d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">d</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">best_k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">k</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="n">best_ks</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">best_k</span><span class="p">;</span><span class="w"></span>
<span class="p">});</span><span class="w"></span></pre><p>The third step of moving every centroid to the average of points is also parallelizable across individual centroids. However, since k is typically not large, one task of doing this update is sufficient.</p><pre class="m-code"><span class="n">taskflow</span><span class="p">.</span><span class="n">emplace</span><span class="p">([</span><span class="o">&amp;</span><span class="p">](){</span><span class="w"></span>
<span class="w"> </span><span class="c1">// sum of points</span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span><span class="w"> </span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">sx</span><span class="p">[</span><span class="n">best_ks</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="n">px</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="n">sy</span><span class="p">[</span><span class="n">best_ks</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="n">py</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">[</span><span class="n">best_ks</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span>
<span class="w"> </span><span class="c1">// average of points</span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="o">&lt;</span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">k</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">auto</span><span class="w"> </span><span class="n">count</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">max</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">[</span><span class="n">k</span><span class="p">]);</span><span class="w"> </span><span class="c1">// turn 0/0 to 0/1</span>
<span class="w"> </span><span class="n">mx</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">sx</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">count</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">my</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">sy</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">count</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="p">});</span><span class="w"></span></pre><p>To describe <code>M</code> iterations, we create a condition task that loops the second step of the algorithm by <code>M</code> times. The return value of zero goes to the first successor which we will connect to the task of the second step later; otherwise, k-means completes.</p><pre class="m-code"><span class="n">taskflow</span><span class="p">.</span><span class="n">emplace</span><span class="p">([</span><span class="n">m</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">M</span><span class="p">]()</span><span class="w"> </span><span class="k">mutable</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="p">(</span><span class="n">m</span><span class="o">++</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">M</span><span class="p">)</span><span class="w"> </span><span class="o">?</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="o">:</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="p">});</span><span class="w"></span></pre><p>The entire code of CPU-parallel k-means is shown below. Here we use an additional storage, <code>best_ks</code>, to record the nearest centroid of a point at an iteration.</p><pre class="m-code"><span class="c1">// N: number of points</span>
<span class="c1">// K: number of clusters</span>
<span class="c1">// M: number of iterations</span>
<span class="c1">// px/py: 2D point vector </span>
<span class="kt">void</span><span class="w"> </span><span class="nf">kmeans_par</span><span class="p">(</span><span class="w"></span>
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">N</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">K</span><span class="p">,</span><span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">M</span><span class="p">,</span><span class="w"> </span><span class="n">cconst</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;&amp;</span><span class="w"> </span><span class="n">px</span><span class="p">,</span><span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;&amp;</span><span class="w"> </span><span class="n">py</span><span class="w"></span>
<span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>

<span class="w"> </span><span class="kt">unsigned</span><span class="w"> </span><span class="n">P</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">12</span><span class="p">;</span><span class="w"> </span><span class="c1">// 12 partitions of the parallel-for graph</span>

<span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Executor</span><span class="w"> </span><span class="n">executor</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Taskflow</span><span class="w"> </span><span class="n">taskflow</span><span class="p">(</span><span class="s">&quot;K-Means&quot;</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="w"> </span><span class="n">c</span><span class="p">(</span><span class="n">K</span><span class="p">),</span><span class="w"> </span><span class="n">best_ks</span><span class="p">(</span><span class="n">N</span><span class="p">);</span><span class="w"></span>
<span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;</span><span class="w"> </span><span class="n">sx</span><span class="p">(</span><span class="n">K</span><span class="p">),</span><span class="w"> </span><span class="n">sy</span><span class="p">(</span><span class="n">K</span><span class="p">),</span><span class="w"> </span><span class="n">mx</span><span class="p">(</span><span class="n">K</span><span class="p">),</span><span class="w"> </span><span class="n">my</span><span class="p">(</span><span class="n">K</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="c1">// initial centroids</span>
<span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Task</span><span class="w"> </span><span class="n">init</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">taskflow</span><span class="p">.</span><span class="n">emplace</span><span class="p">([</span><span class="o">&amp;</span><span class="p">](){</span><span class="w"></span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">i</span><span class="o">&lt;</span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">i</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">mx</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">px</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="n">my</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">py</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">}).</span><span class="n">name</span><span class="p">(</span><span class="s">&quot;init&quot;</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="c1">// clear the storage</span>
<span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Task</span><span class="w"> </span><span class="n">clean_up</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">taskflow</span><span class="p">.</span><span class="n">emplace</span><span class="p">([</span><span class="o">&amp;</span><span class="p">](){</span><span class="w"></span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="o">&lt;</span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">k</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">sx</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mf">0.0f</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">sy</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mf">0.0f</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">}).</span><span class="n">name</span><span class="p">(</span><span class="s">&quot;clean_up&quot;</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="c1">// update cluster</span>
<span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Task</span><span class="w"> </span><span class="n">pf</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">taskflow</span><span class="p">.</span><span class="n">for_each_index</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">N</span><span class="p">,</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="p">[</span><span class="o">&amp;</span><span class="p">](</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">){</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">px</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">y</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">py</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">best_d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">numeric_limits</span><span class="o">&lt;</span><span class="kt">float</span><span class="o">&gt;::</span><span class="n">max</span><span class="p">();</span><span class="w"></span>
<span class="w"> </span><span class="kt">int</span><span class="w"> </span><span class="n">best_k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">k</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="kt">float</span><span class="w"> </span><span class="n">d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">L2</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">y</span><span class="p">,</span><span class="w"> </span><span class="n">mx</span><span class="p">[</span><span class="n">k</span><span class="p">],</span><span class="w"> </span><span class="n">my</span><span class="p">[</span><span class="n">k</span><span class="p">]);</span><span class="w"></span>
<span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">d</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">best_d</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">best_d</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">d</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">best_k</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">k</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="n">best_ks</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">best_k</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}).</span><span class="n">name</span><span class="p">(</span><span class="s">&quot;parallel-for&quot;</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Task</span><span class="w"> </span><span class="n">update_cluster</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">taskflow</span><span class="p">.</span><span class="n">emplace</span><span class="p">([</span><span class="o">&amp;</span><span class="p">](){</span><span class="w"></span>
<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">i</span><span class="o">&lt;</span><span class="n">N</span><span class="p">;</span><span class="w"> </span><span class="n">i</span><span class="o">++</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="n">sx</span><span class="p">[</span><span class="n">best_ks</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="n">px</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="n">sy</span><span class="p">[</span><span class="n">best_ks</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="n">py</span><span class="p">[</span><span class="n">i</span><span class="p">];</span><span class="w"></span>
<span class="w"> </span><span class="n">c</span><span class="w"> </span><span class="p">[</span><span class="n">best_ks</span><span class="p">[</span><span class="n">i</span><span class="p">]]</span><span class="w"> </span><span class="o">+=</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>

<span class="w"> </span><span class="k">for</span><span class="p">(</span><span class="kt">int</span><span class="w"> </span><span class="n">k</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="w"> </span><span class="n">k</span><span class="o">&lt;</span><span class="n">K</span><span class="p">;</span><span class="w"> </span><span class="o">++</span><span class="n">k</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">auto</span><span class="w"> </span><span class="n">count</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">max</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="n">c</span><span class="p">[</span><span class="n">k</span><span class="p">]);</span><span class="w"> </span><span class="c1">// turn 0/0 to 0/1</span>
<span class="w"> </span><span class="n">mx</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">sx</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">count</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="n">my</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">sy</span><span class="p">[</span><span class="n">k</span><span class="p">]</span><span class="w"> </span><span class="o">/</span><span class="w"> </span><span class="n">count</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="w"> </span><span class="p">}).</span><span class="n">name</span><span class="p">(</span><span class="s">&quot;update_cluster&quot;</span><span class="p">);</span><span class="w"></span>
<span class="w"> </span>
<span class="w"> </span><span class="c1">// convergence check</span>
<span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Task</span><span class="w"> </span><span class="n">condition</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">taskflow</span><span class="p">.</span><span class="n">emplace</span><span class="p">([</span><span class="n">m</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="n">M</span><span class="p">]()</span><span class="w"> </span><span class="k">mutable</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="p">(</span><span class="n">m</span><span class="o">++</span><span class="w"> </span><span class="o">&lt;</span><span class="w"> </span><span class="n">M</span><span class="p">)</span><span class="w"> </span><span class="o">?</span><span class="w"> </span><span class="mi">0</span><span class="w"> </span><span class="o">:</span><span class="w"> </span><span class="mi">1</span><span class="p">;</span><span class="w"></span>
<span class="w"> </span><span class="p">}).</span><span class="n">name</span><span class="p">(</span><span class="s">&quot;converged?&quot;</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="n">init</span><span class="p">.</span><span class="n">precede</span><span class="p">(</span><span class="n">clean_up</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="n">clean_up</span><span class="p">.</span><span class="n">precede</span><span class="p">(</span><span class="n">pf</span><span class="p">);</span><span class="w"></span>
<span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">precede</span><span class="p">(</span><span class="n">update_cluster</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="n">condition</span><span class="p">.</span><span class="n">precede</span><span class="p">(</span><span class="n">clean_up</span><span class="p">)</span><span class="w"></span>
<span class="w"> </span><span class="p">.</span><span class="n">succeed</span><span class="p">(</span><span class="n">update_cluster</span><span class="p">);</span><span class="w"></span>

<span class="w"> </span><span class="n">executor</span><span class="p">.</span><span class="n">run</span><span class="p">(</span><span class="n">taskflow</span><span class="p">).</span><span class="n">wait</span><span class="p">();</span><span class="w"></span>
<span class="p">}</span><span class="w"></span></pre><p>The taskflow consists of two parts, a <code>clean_up</code> task and a parallel-for graph. The former cleans up the storage <code>sx</code>, <code>sy</code>, and <code>c</code> that are used to average points for new centroids, and the later parallelizes the searching for nearest centroids across individual points using 12 tasks (may vary depending on the machine). If the iteration count is smaller than <code>M</code>, the condition task returns 0 to let the execution path go back to <code>clean_up</code>. Otherwise, it returns 1 to stop (i.e., no successor tasks at index 1). The taskflow graph is illustrated below:</p><div class="m-graph"><svg style="width: 65.500rem; height: 74.300rem;" viewBox="0.00 0.00 655.42 743.00">
<g transform="scale(1 1) rotate(0) translate(4 739)">
<title>Taskflow</title>
<g class="m-cluster">
<title>cluster_p0x1dcb6e0</title>
<polygon points="8,-8 8,-727 241.4564,-727 241.4564,-8 8,-8"/>
<text text-anchor="middle" x="124.7282" y="-715" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">Subflow: parallel&#45;for</text>
</g>
<g class="m-node m-flat">
<title>p0x1dcb4c0</title>
<ellipse cx="473.0106" cy="-421" rx="27" ry="18"/>
<text text-anchor="middle" x="473.0106" y="-418.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">init</text>
</g>
<g class="m-node m-flat">
<title>p0x1dcb5d0</title>
<ellipse cx="612.1025" cy="-375" rx="35.1405" ry="18"/>
<text text-anchor="middle" x="612.1025" y="-372.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">clean_up</text>
</g>
<g class="m-edge">
<title>p0x1dcb4c0&#45;&gt;p0x1dcb5d0</title>
<path d="M497.2385,-412.9874C518.0347,-406.1098 548.4065,-396.0653 572.6966,-388.0322"/>
<polygon points="573.9539,-391.3029 582.3491,-384.8399 571.7559,-384.6569 573.9539,-391.3029"/>
</g>
<g class="m-node m-flat">
<title>p0x1dcb6e0</title>
<ellipse cx="191.6614" cy="-358" rx="41.5911" ry="18"/>
<text text-anchor="middle" x="191.6614" y="-355.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">parallel&#45;for</text>
</g>
<g class="m-edge">
<title>p0x1dcb5d0&#45;&gt;p0x1dcb6e0</title>
<path d="M576.7397,-373.5701C502.5679,-370.5711 330.439,-363.6113 243.6594,-360.1025"/>
<polygon points="243.6452,-356.5991 233.512,-359.6922 243.3624,-363.5934 243.6452,-356.5991"/>
</g>
<g class="m-node m-flat">
<title>p0x1dcb7f0</title>
<ellipse cx="322.8474" cy="-329" rx="52.2822" ry="18"/>
<text text-anchor="middle" x="322.8474" y="-326.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">update_cluster</text>
</g>
<g class="m-edge">
<title>p0x1dcb6e0&#45;&gt;p0x1dcb7f0</title>
<path d="M228.9031,-349.7673C241.2173,-347.0452 255.1824,-343.958 268.5086,-341.0122"/>
<polygon points="269.5279,-344.3714 278.5367,-338.7953 268.0169,-337.5364 269.5279,-344.3714"/>
</g>
<g class="m-node">
<title>p0x1dcb900</title>
<polygon points="473.0106,-347 412.4654,-329 473.0106,-311 533.5557,-329 473.0106,-347"/>
<text text-anchor="middle" x="473.0106" y="-326.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">converged?</text>
</g>
<g class="m-edge">
<title>p0x1dcb7f0&#45;&gt;p0x1dcb900</title>
<path d="M375.3672,-329C384.0316,-329 393.1379,-329 402.1623,-329"/>
<polygon points="402.2886,-332.5001 412.2886,-329 402.2885,-325.5001 402.2886,-332.5001"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000b50</title>
<ellipse cx="45.4331" cy="-682" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-679.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_0</text>
</g>
<g class="m-edge">
<title>p0x7fd610000b50&#45;&gt;p0x1dcb6e0</title>
<path d="M62.9675,-668.3116C67.2604,-664.355 71.5644,-659.7985 74.8663,-655 135.9443,-566.2373 171.6244,-440.9464 185.2481,-385.8438"/>
<polygon points="188.6574,-386.6358 187.6082,-376.093 181.8539,-384.989 188.6574,-386.6358"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000c60</title>
<ellipse cx="45.4331" cy="-628" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-625.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_1</text>
</g>
<g class="m-edge">
<title>p0x7fd610000c60&#45;&gt;p0x1dcb6e0</title>
<path d="M62.7393,-614.1485C67.034,-610.1931 71.3959,-605.6781 74.8663,-601 127.2191,-530.4291 165.5956,-432.6887 182.3416,-385.5741"/>
<polygon points="185.6745,-386.6462 185.6755,-376.0514 179.0677,-384.3332 185.6745,-386.6462"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000d70</title>
<ellipse cx="45.4331" cy="-574" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-571.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_2</text>
</g>
<g class="m-edge">
<title>p0x7fd610000d70&#45;&gt;p0x1dcb6e0</title>
<path d="M62.4118,-559.8919C66.7091,-555.9385 71.1541,-551.4886 74.8663,-547 118.8306,-493.8406 158.3695,-422.7142 178.2093,-384.6693"/>
<polygon points="181.3415,-386.2319 182.8196,-375.7407 175.1217,-383.0203 181.3415,-386.2319"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000e80</title>
<ellipse cx="45.4331" cy="-520" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-517.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_3</text>
</g>
<g class="m-edge">
<title>p0x7fd610000e80&#45;&gt;p0x1dcb6e0</title>
<path d="M61.943,-505.4716C66.2439,-501.5214 70.8079,-497.1782 74.8663,-493 110.4817,-456.3333 148.6863,-410.8751 171.3596,-383.1744"/>
<polygon points="174.2729,-385.14 177.8775,-375.1772 168.8467,-380.7176 174.2729,-385.14"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610000f90</title>
<ellipse cx="45.4331" cy="-466" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-463.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_4</text>
</g>
<g class="m-edge">
<title>p0x7fd610000f90&#45;&gt;p0x1dcb6e0</title>
<path d="M63.6574,-452.5401C88.3249,-434.3214 132.6364,-401.5941 162.1001,-379.8331"/>
<polygon points="164.3936,-382.4903 170.3582,-373.7339 160.2349,-376.8596 164.3936,-382.4903"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100010a0</title>
<ellipse cx="45.4331" cy="-412" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-409.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_5</text>
</g>
<g class="m-edge">
<title>p0x7fd6100010a0&#45;&gt;p0x1dcb6e0</title>
<path d="M69.2527,-403.2038C91.1398,-395.1212 124.0586,-382.9647 150.2479,-373.2934"/>
<polygon points="151.7503,-376.4697 159.9186,-369.7221 149.3254,-369.9031 151.7503,-376.4697"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100011b0</title>
<ellipse cx="45.4331" cy="-358" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-355.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_6</text>
</g>
<g class="m-edge">
<title>p0x7fd6100011b0&#45;&gt;p0x1dcb6e0</title>
<path d="M72.5949,-358C91.3605,-358 116.9179,-358 139.544,-358"/>
<polygon points="139.6986,-361.5001 149.6986,-358 139.6985,-354.5001 139.6986,-361.5001"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100012c0</title>
<ellipse cx="45.4331" cy="-304" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-301.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_7</text>
</g>
<g class="m-edge">
<title>p0x7fd6100012c0&#45;&gt;p0x1dcb6e0</title>
<path d="M69.2527,-312.7962C91.1398,-320.8788 124.0586,-333.0353 150.2479,-342.7066"/>
<polygon points="149.3254,-346.0969 159.9186,-346.2779 151.7503,-339.5303 149.3254,-346.0969"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100013d0</title>
<ellipse cx="45.4331" cy="-250" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-247.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_8</text>
</g>
<g class="m-edge">
<title>p0x7fd6100013d0&#45;&gt;p0x1dcb6e0</title>
<path d="M63.6574,-263.4599C88.3249,-281.6786 132.6364,-314.4059 162.1001,-336.1669"/>
<polygon points="160.2349,-339.1404 170.3582,-342.2661 164.3936,-333.5097 160.2349,-339.1404"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100014e0</title>
<ellipse cx="45.4331" cy="-196" rx="27" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-193.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_9</text>
</g>
<g class="m-edge">
<title>p0x7fd6100014e0&#45;&gt;p0x1dcb6e0</title>
<path d="M61.943,-210.5284C66.2439,-214.4786 70.8079,-218.8218 74.8663,-223 110.4817,-259.6667 148.6863,-305.1249 171.3596,-332.8256"/>
<polygon points="168.8467,-335.2824 177.8775,-340.8228 174.2729,-330.86 168.8467,-335.2824"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd6100015f0</title>
<ellipse cx="45.4331" cy="-142" rx="29.3664" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-139.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_10</text>
</g>
<g class="m-edge">
<title>p0x7fd6100015f0&#45;&gt;p0x1dcb6e0</title>
<path d="M63.0266,-156.6762C67.1307,-160.4853 71.3309,-164.7251 74.8663,-169 118.8306,-222.1594 158.3695,-293.2858 178.2093,-331.3307"/>
<polygon points="175.1217,-332.9797 182.8196,-340.2593 181.3415,-329.7681 175.1217,-332.9797"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610001700</title>
<ellipse cx="45.4331" cy="-88" rx="29.3664" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-85.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_11</text>
</g>
<g class="m-edge">
<title>p0x7fd610001700&#45;&gt;p0x1dcb6e0</title>
<path d="M63.3532,-102.4203C67.4474,-106.2372 71.5611,-110.5447 74.8663,-115 127.2191,-185.5709 165.5956,-283.3113 182.3416,-330.4259"/>
<polygon points="179.0677,-331.6668 185.6755,-339.9486 185.6745,-329.3538 179.0677,-331.6668"/>
</g>
<g class="m-node m-flat">
<title>p0x7fd610001810</title>
<ellipse cx="45.4331" cy="-34" rx="29.3664" ry="18"/>
<text text-anchor="middle" x="45.4331" y="-31.5" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">pfg_12</text>
</g>
<g class="m-edge">
<title>p0x7fd610001810&#45;&gt;p0x1dcb6e0</title>
<path d="M63.5808,-48.2577C67.6681,-52.0795 71.7217,-56.43 74.8663,-61 135.9443,-149.7627 171.6244,-275.0536 185.2481,-330.1562"/>
<polygon points="181.8539,-331.011 187.6082,-339.907 188.6574,-329.3642 181.8539,-331.011"/>
</g>
<g class="m-edge">
<title>p0x1dcb900&#45;&gt;p0x1dcb5d0</title>
<path stroke-dasharray="5,2" d="M509.366,-336.2239C524.8076,-339.7212 542.8801,-344.3877 558.7827,-350 565.0464,-352.2106 571.565,-354.9093 577.8057,-357.706"/>
<polygon points="576.7638,-361.0815 587.3071,-362.1255 579.7161,-354.7345 576.7638,-361.0815"/>
<text text-anchor="middle" x="555.2827" y="-353" font-family="Helvetica,sans-Serif" font-size="10.00" fill="#000000">0</text>
</g>
</g>
</svg>
</div><p>The scheduler starts with <code>init</code>, moves on to <code>clean_up</code>, and then enters the parallel-for task <code>paralle-for</code> that spawns a subflow of 12 workers to perform parallel iterations. When <code>parallel-for</code> completes, it updates the cluster centroids and checks if they have converged through a condition task. If not, the condition task informs the scheduler to go back to <code>clean_up</code> and then <code>parallel-for</code>; otherwise, it returns a nominal index to stop the scheduler.</p></section><section id="KMeansBenchmarking"><h2><a href="#KMeansBenchmarking">Benchmarking</a></h2><p>Based on the discussion above, we compare the runtime of computing various k-means problem sizes between a sequential CPU and parallel CPUs on a machine of 12 Intel i7-8700 CPUs at 3.2 GHz.</p><table class="m-table"><thead><tr><th>N</th><th>K</th><th>M</th><th>CPU Sequential</th><th>CPU Parallel</th></tr></thead><tbody><tr><td>10</td><td>5</td><td>10</td><td>0.14 ms</td><td>77 ms</td></tr><tr><td>100</td><td>10</td><td>100</td><td>0.56 ms</td><td>86 ms</td></tr><tr><td>1000</td><td>10</td><td>1000</td><td>10 ms</td><td>98 ms</td></tr><tr><td>10000</td><td>10</td><td>10000</td><td>1006 ms</td><td>713 ms</td></tr><tr><td>100000</td><td>10</td><td>100000</td><td>102483 ms</td><td>49966 ms</td></tr></tbody></table><p>When the number of points is larger than 10K, the parallel CPU implementation starts to outperform the sequential CPU implementation.</p></section>
 </div>
 </div>
 </div>
</article></main>
<div class="m-doc-search" id="search">
 <a href="#!" onclick="return hideSearch()"></a>
 <div class="m-container">
 <div class="m-row">
 <div class="m-col-m-8 m-push-m-2">
 <div class="m-doc-search-header m-text m-small">
 <div><span class="m-label m-default">Tab</span> / <span class="m-label m-default">T</span> to search, <span class="m-label m-default">Esc</span> to close</div>
 <div id="search-symbolcount">&hellip;</div>
 </div>
 <div class="m-doc-search-content">
 <form>
 <input type="search" name="q" id="search-input" placeholder="Loading &hellip;" disabled="disabled" autofocus="autofocus" autocomplete="off" spellcheck="false" />
 </form>
 <noscript class="m-text m-danger m-text-center">Unlike everything else in the docs, the search functionality <em>requires</em> JavaScript.</noscript>
 <div id="search-help" class="m-text m-dim m-text-center">
 <p class="m-noindent">Search for symbols, directories, files, pages or
 modules. You can omit any prefix from the symbol or file path; adding a
 <code>:</code> or <code>/</code> suffix lists all members of given symbol or
 directory.</p>
 <p class="m-noindent">Use <span class="m-label m-dim">&darr;</span>
 / <span class="m-label m-dim">&uarr;</span> to navigate through the list,
 <span class="m-label m-dim">Enter</span> to go.
 <span class="m-label m-dim">Tab</span> autocompletes common prefix, you can
 copy a link to the result using <span class="m-label m-dim">⌘</span>
 <span class="m-label m-dim">L</span> while <span class="m-label m-dim">⌘</span>
 <span class="m-label m-dim">M</span> produces a Markdown link.</p>
 </div>
 <div id="search-notfound" class="m-text m-warning m-text-center">Sorry, nothing was found.</div>
 <ul id="search-results"></ul>
 </div>
 </div>
 </div>
 </div>
</div>
<script src="search-v2.js"></script>
<script src="searchdata-v2.js" async="async"></script>
<footer><nav>
 <div class="m-container">
 <div class="m-row">
 <div class="m-col-l-10 m-push-l-1">
 <p>Taskflow handbook is part of the <a href="https://taskflow.github.io">Taskflow project</a>, copyright © <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>, 2018&ndash;2023.<br />Generated by <a href="https://doxygen.org/">Doxygen</a> 1.8.14 and <a href="https://mcss.mosra.cz/">m.css</a>.</p>
 </div>
 </div>
 </div>
</nav></footer>
</body>
</html>