kNN概述

機(jī)器学習算法：

機(jī)器学習算法分(fēn)为(wèi)两(liǎng)類(lèi)：懒惰和(hé)急切(qiè)学習。懒惰学習算法包(bāo)括存儲訓練數據(jù)并在(zài)接收(shōu)到(dào)新的(de)輸入(rù)數據(jù)时(shí)計(jì)算一(yī)些結果(guǒ)，而(ér)急切(qiè)訓練包(bāo)括預先(xiān)計(jì)算算法并将其用(yòng)于(yú)新的(de)輸入(rù)數據(jù)。这(zhè)些可(kě)以(yǐ)進(jìn)一(yī)步劃(huà)分(fēn)为(wèi)有(yǒu)監督或(huò)无監督学習。監督学習要(yào)求测試數據(jù)已經(jīng)預先(xiān)分(fēn)類(lèi)，而(ér)无監督学習則沒(méi)有(yǒu)。

分(fēn)類(lèi)：

分(fēn)類(lèi)是(shì)一(yī)種(zhǒng)有(yǒu)監督且通(tòng)常懒惰的(de)学習方(fāng)法。一(yī)般来(lái)说(shuō)，这(zhè)个(gè)过(guò)程分(fēn)为(wèi)两(liǎng)个(gè)階(jiē)段(duàn)：培訓和(hé)分(fēn)類(lèi)。培訓階(jiē)段(duàn)包(bāo)括将預先(xiān)分(fēn)類(lèi)的(de)數據(jù)輸入(rù)模型，以(yǐ)開(kāi)發(fà)可(kě)在(zài)分(fēn)類(lèi)階(jiē)段(duàn)使用(yòng)的(de)數據(jù)集。分(fēn)類(lèi)階(jiē)段(duàn)包(bāo)括将新的(de)，未分(fēn)類(lèi)的(de)數據(jù)輸入(rù)到(dào)訓練模型中(zhōng)并嘗試为(wèi)其添加新标(biāo)签(qiān)。流行的(de)分(fēn)類(lèi)算法包(bāo)括Naive Bayes，支持(chí)向(xiàng)量(liàng)機(jī)以(yǐ)及(jí)最(zuì)近(jìn)鄰算法。

kNN算法：

我(wǒ)们(men)的(de)項目側重(zhòng)于(yú)实現(xiàn)k-Nearest Neighbor（kNN）算法。與(yǔ)大多(duō)數分(fēn)類(lèi)器一(yī)樣(yàng)，該算法在(zài)訓練階(jiē)段(duàn)接收(shōu)預先(xiān)分(fēn)類(lèi)的(de)數據(jù)。在(zài)分(fēn)類(lèi)階(jiē)段(duàn)，算法确定(dìng)新测試數據(jù)與(yǔ)整个(gè)訓練集之間(jiān)的(de)距離，并查看(kàn)k，用(yòng)戶定(dìng)義的(de)常數，最(zuì)近(jìn)鄰居，并選擇發(fà)生(shēng)率最(zuì)高(gāo)的(de)鄰居。換句(jù)話(huà)说(shuō)，我(wǒ)们(men)可(kě)以(yǐ)将算法分(fēn)为(wèi)三(sān)个(gè)主(zhǔ)要(yào)階(jiē)段(duàn)：距離計(jì)算，排序和(hé)選擇。

kNN算法

高(gāo)級設計(jì)：

kNN硬(yìng)件(jiàn)的(de)設計(jì)包(bāo)括三(sān)个(gè)主(zhǔ)要(yào)模块(kuài)：距離計(jì)算器，分(fēn)揀機(jī)和(hé)選擇器。

管(guǎn)道(dào)：

我(wǒ)们(men)的(de)分(fēn)類(lèi)器管(guǎn)道(dào)包(bāo)括單周期(qī)距離計(jì)算器，單周期(qī)分(fēn)揀機(jī)和(hé)k循环(huán)選擇器。換句(jù)話(huà)说(shuō)，分(fēn)類(lèi)器從我(wǒ)们(men)的(de)訓練集接收(shōu)分(fēn)類(lèi)數據(jù)块(kuài)以(yǐ)及(jí)新的(de)测試數據(jù)块(kuài)，并在(zài)一(yī)个(gè)周期(qī)中(zhōng)将其放(fàng)置在(zài)重(zhòng)新排序的(de)列表(biǎo)中(zhōng)时(shí)計(jì)算距離。該算法对(duì)訓練集中(zhōng)的(de)每个(gè)數據(jù)块(kuài)執行該計(jì)算，因(yīn)此(cǐ)需要(yào)n个(gè)周期(qī)来(lái)計(jì)算新的(de)测試數據(jù)块(kuài)與(yǔ)我(wǒ)们(men)的(de)訓練集中(zhōng)的(de)n个(gè)分(fēn)類(lèi)數據(jù)块(kuài)之間(jiān)的(de)距離。之後(hòu)，我(wǒ)们(men)的(de)管(guǎn)道(dào)需要(yào)k个(gè)周期(qī)来(lái)查看(kàn)排序列表(biǎo)中(zhōng)的(de)k个(gè)最(zuì)近(jìn)鄰居，并将其輸出(chū)为(wèi)我(wǒ)们(men)测試块(kuài)的(de)新标(biāo)签(qiān)。

图(tú)：管(guǎn)道(dào)

这(zhè)个(gè)kNN管(guǎn)道(dào)專門(mén)用(yòng)于(yú)图(tú)像識别，專門(mén)用(yòng)于(yú)我(wǒ)们(men)如(rú)何編碼图(tú)像。如(rú)上(shàng)所(suǒ)述，我(wǒ)们(men)已決定(dìng)将图(tú)像編碼为(wèi)64,16位字(zì)，其充當強(qiáng)度(dù)直(zhí)方(fāng)图(tú)。将其映射到(dào)我(wǒ)们(men)的(de)硬(yìng)件(jiàn)，我(wǒ)们(men)的(de)距離計(jì)算器包(bāo)括对(duì)訓練數據(jù)块(kuài)的(de)64个(gè)字(zì)中(zhōng)的(de)每个(gè)字(zì)與(yǔ)新测試數據(jù)块(kuài)之間(jiān)的(de)差异(yì)求和(hé)。我(wǒ)们(men)的(de)排序包(bāo)括獲取(qǔ)計(jì)算的(de)距離并維護所(suǒ)有(yǒu)訓練數據(jù)块(kuài)的(de)排序列表(biǎo)。我(wǒ)们(men)的(de)選擇器查看(kàn)排序列表(biǎo)中(zhōng)的(de)前(qián)k个(gè)元(yuán)素并輸出(chū)最(zuì)高(gāo)的(de)元(yuán)素。

图(tú)：框图(tú)

距離：

距離計(jì)算器經(jīng)曆了(le)许多(duō)次(cì)叠代(dài)設計(jì)。第(dì)一(yī)个(gè)設計(jì)涉及(jí)一(yī)个(gè)12周期(qī)管(guǎn)道(dào)，以(yǐ)減少(shǎo)使用(yòng)的(de)加法器總(zǒng)數，并希望允许更(gèng)多(duō)的(de)并行化(huà)。在(zài)对(duì)該設計(jì)進(jìn)行了(le)一(yī)些初步测試之後(hòu)，我(wǒ)们(men)轉(zhuǎn)向(xiàng)了(le)單周期(qī)組合設計(jì)，因(yīn)为(wèi)用(yòng)于(yú)处理狀态的(de)額外(wài)邏輯單元(yuán)占用(yòng)了(le)比預期(qī)更(gèng)多(duō)的(de)空間(jiān)。最(zuì)終(zhōng)距離模块(kuài)簡單地(dì)为(wèi)訓練數據(jù)和(hé)测試數據(jù)提(tí)供64位，16位字(zì)，两(liǎng)者(zhě)均表(biǎo)示为(wèi)1024位輸入(rù)，并行執行64次(cì)減法，然後(hòu)進(jìn)行60次(cì)加法。

分(fēn)類(lèi)：

排序算法也(yě)經(jīng)曆了(le)多(duō)次(cì)叠代(dài)。最(zuì)初的(de)設計(jì)涉及(jí)每个(gè)數據(jù)的(de)两(liǎng)个(gè)周期(qī)/两(liǎng)个(gè)階(jiē)段(duàn)。第(dì)一(yī)个(gè)周期(qī)旨在(zài)決定(dìng)新數據(jù)的(de)去(qù)向(xiàng)，以(yǐ)及(jí)为(wèi)了(le)容納新數據(jù)而(ér)必須移位哪些數據(jù)，第(dì)二(èr)个(gè)周期(qī)是(shì)在(zài)正(zhèng)确的(de)位置解(jiě)決所(suǒ)有(yǒu)數據(jù)。我(wǒ)们(men)挑戰自(zì)己改進(jìn)設計(jì)。这(zhè)一(yī)挑戰背後(hòu)的(de)主(zhǔ)要(yào)動(dòng)機(jī)是(shì)數據(jù)被(bèi)串聯送入(rù)分(fēn)揀機(jī)，我(wǒ)们(men)的(de)主(zhǔ)要(yào)目标(biāo)是(shì)顯示現(xiàn)有(yǒu)算法的(de)硬(yìng)件(jiàn)加速。最(zuì)終(zhōng)实現(xiàn)在(zài)單个(gè)周期(qī)中(zhōng)对(duì)傳入(rù)排序模块(kuài)的(de)數據(jù)進(jìn)行排序，确定(dìng)新數據(jù)所(suǒ)屬的(de)位置以(yǐ)及(jí)如(rú)何在(zài)同(tóng)一(yī)周期(qī)中(zhōng)替換先(xiān)前(qián)的(de)數據(jù)。

分(fēn)揀機(jī)的(de)最(zuì)終(zhōng)实施部(bù)分(fēn)源于(yú)我(wǒ)们(men)在(zài)之前(qián)的(de)实验(yàn)室(shì)中(zhōng)实施的(de)鼓式合成(chéng)器。鼓合成(chéng)器具有(yǒu)代(dài)表(biǎo)鼓上(shàng)节(jié)點(diǎn)的(de)單元(yuán)，并且可(kě)以(yǐ)訪問(wèn)關(guān)于(yú)其相鄰單元(yuán)的(de)信(xìn)息，这(zhè)是(shì)确定(dìng)其下(xià)一(yī)个(gè)值所(suǒ)必需的(de)。類(lèi)似地(dì)，分(fēn)揀機(jī)由(yóu)一(yī)組桶(tǒng)模块(kuài)組成(chéng)，这(zhè)些模块(kuài)是(shì)为(wèi)了(le)在(zài)數據(jù)進(jìn)入(rù)时(shí)正(zhèng)确对(duì)數據(jù)進(jìn)行分(fēn)類(lèi)而(ér)生(shēng)成(chéng)的(de)。桶(tǒng)中(zhōng)包(bāo)含有(yǒu)關(guān)新數據(jù)的(de)信(xìn)息，自(zì)身(shēn)的(de)狀态和(hé)值，以(yǐ)及(jí)狀态和(hé)數據(jù)。上(shàng)面(miàn)的(de)桶(tǒng)。

每个(gè)桶(tǒng)模块(kuài)有(yǒu)bucket_data寄存器来(lái)存儲數據(jù)，并且bucket_full注册跟蹤的(de)狀态（滿或(huò)空）。这(zhè)两(liǎng)个(gè)寄存器都連(lián)接到(dào)桶(tǒng)模块(kuài)的(de)輸出(chū)。铲斗(dǒu)模块(kuài)的(de)輸入(rù)是(shì)时(shí)鐘(zhōng)，重(zhòng)置，和(hé)使能(néng)，以(yǐ)及(jí)NEW_DATA代(dài)表(biǎo)進(jìn)来(lái)的(de)數據(jù)輸入(rù)，以(yǐ)及(jí)above_data和(hé)above_full分(fēn)别跟蹤數據(jù)和(hé)狀态上(shàng)述铲斗(dǒu)的(de)。

在(zài)每个(gè)时(shí)鐘(zhōng)周期(qī)，存儲桶(tǒng)将決定(dìng)存儲哪些數據(jù)。每个(gè)桶(tǒng)最(zuì)初（并且在(zài)重(zhòng)置时(shí)）設置为(wèi)空并且具有(yǒu)存儲值“0”。如(rú)果(guǒ)上(shàng)面(miàn)的(de)桶(tǒng)是(shì)空的(de)，桶(tǒng)沒(méi)有(yǒu)存儲任何東(dōng)西(xī)，并保持(chí)空。最(zuì)上(shàng)面(miàn)的(de)桶(tǒng)将above_full輸入(rù)硬(yìng)連(lián)接到(dào)full，并且above_data輸入(rù)硬(yìng)連(lián)接到(dào)0（最(zuì)小的(de)歐幾(jǐ)里(lǐ)德距離）。如(rú)果(guǒ)當前(qián)桶(tǒng)为(wèi)空，則上(shàng)述桶(tǒng)已滿，上(shàng)述桶(tǒng)數據(jù)不(bù)大于(yú)新數據(jù)，桶(tǒng)存儲新數據(jù)。如(rú)果(guǒ)當前(qián)桶(tǒng)數據(jù)大于(yú)新數據(jù)且上(shàng)述桶(tǒng)數據(jù)不(bù)是(shì)，則桶(tǒng)也(yě)存儲新數據(jù)。但是(shì)，如(rú)果(guǒ)上(shàng)述存儲桶(tǒng)數據(jù)在(zài)任何时(shí)候都大于(yú)新數據(jù)，則當前(qián)存儲桶(tǒng)始終(zhōng)存儲上(shàng)述存儲桶(tǒng)數據(jù)。

選擇：

選擇模块(kuài)是(shì)整个(gè)过(guò)程的(de)瓶颈。在(zài)对(duì)所(suǒ)有(yǒu)數據(jù)進(jìn)行排序後(hòu)，選擇器必須查看(kàn)前(qián)k个(gè)數據(jù)并選擇哪个(gè)标(biāo)記(jì)最(zuì)常見(jiàn)。換句(jù)話(huà)说(shuō)，選擇器将選擇在(zài)與(yǔ)給(gěi)定(dìng)图(tú)像具有(yǒu)最(zuì)小距離的(de)图(tú)像中(zhōng)最(zuì)常表(biǎo)示的(de)标(biāo)签(qiān) - 選擇k个(gè)最(zuì)近(jìn)鄰居的(de)模式。選擇器等待分(fēn)揀機(jī)完成(chéng)，叠代(dài)通(tòng)过(guò)每个(gè)前(qián)k个(gè)數據(jù)块(kuài)一(yī)次(cì)，然後(hòu)，在(zài)下(xià)一(yī)个(gè)循环(huán)中(zhōng)，确定(dìng)它(tā)们(men)中(zhōng)最(zuì)常出(chū)現(xiàn)的(de)标(biāo)签(qiān)。我(wǒ)们(men)還(huán)改進(jìn)了(le)設計(jì)，使選擇器不(bù)僅輸出(chū)選擇，而(ér)且還(huán)以(yǐ)最(zuì)多(duō)k个(gè)匹(pǐ)配數據(jù)集的(de)形式輸出(chū)置信(xìn)度(dù)。

图(tú)：選擇的(de)百(bǎi)分(fēn)比準确度(dù)

設計(jì)結果(guǒ)

性(xìng)能(néng)和(hé)加速：

最(zuì)終(zhōng)設計(jì)在(zài)性(xìng)能(néng)方(fāng)面(miàn)有(yǒu)了(le)很大的(de)提(tí)升(shēng)。設計(jì)的(de)第(dì)一(yī)次(cì)叠代(dài)涉及(jí)使用(yòng)PIO引脚将图(tú)像直(zhí)方(fāng)图(tú)傳遞給(gěi)HPS，然後(hòu)HPS将運行kNN分(fēn)類(lèi)器。在(zài)性(xìng)能(néng)計(jì)算方(fāng)面(miàn)，对(duì)于(yú)每个(gè)图(tú)像，此(cǐ)設計(jì)需要(yào)叠代(dài)64个(gè)元(yuán)素阵(zhèn)列并執行減法，否定(dìng)和(hé)滾動(dòng)添加，然後(hòu)執行內(nèi)存写入(rù)。換句(jù)話(huà)说(shuō)，我(wǒ)们(men)将有(yǒu)两(liǎng)个(gè)主(zhǔ)要(yào)的(de)for循环(huán)，它(tā)们(men)将編譯成(chéng)至(zhì)少(shǎo)512个(gè)ARM指令（不(bù)計(jì)算跳轉(zhuǎn)和(hé)控制流邏輯）。在(zài)此(cǐ)之後(hòu)，我(wǒ)们(men)必須对(duì)數組進(jìn)行排序，即O（nlogn）就(jiù)图(tú)像的(de)數量(liàng)而(ér)言，就(jiù)指令而(ér)言，这(zhè)可(kě)以(yǐ)變(biàn)化(huà)，但至(zhì)少(shǎo)是(shì)元(yuán)素的(de)數量(liàng)乘以(yǐ)其日(rì)志。最(zuì)後(hòu)，它(tā)必須重(zhòng)複并計(jì)算相对(duì)于(yú)所(suǒ)選擇的(de)k 的(de)最(zuì)近(jìn)鄰，即O（k）。換句(jù)話(huà)说(shuō)，我(wǒ)们(men)将至(zhì)少(shǎo)采用(yòng)（512 + 896）* n + k个(gè)周期(qī)，其中(zhōng)n是(shì)存儲在(zài)存儲器中(zhōng)的(de)面(miàn)數，k是(shì)所(suǒ)選擇的(de)k。

相比之下(xià)，FPGA計(jì)算距離并在(zài)1个(gè)周期(qī)內(nèi)保持(chí)排序列表(biǎo)，然後(hòu)需要(yào)k个(gè)周期(qī)進(jìn)行選擇。換句(jù)話(huà)说(shuō)，我(wǒ)们(men)采用(yòng)有(yǒu)界n + k个(gè)循环(huán)，其中(zhōng)n是(shì)图(tú)像的(de)數量(liàng)并且選擇k。正(zhèng)因(yīn)为(wèi)如(rú)此(cǐ)，我(wǒ)们(men)預测原始周期(qī)的(de)加速速度(dù)約为(wèi)1000倍，而(ér)FPGA的(de)时(shí)鐘(zhōng)速度(dù)則較慢(màn)。得到(dào)官方(fāng)結果(guǒ)後(hòu)，我(wǒ)们(men)看(kàn)到(dào)分(fēn)類(lèi)器在(zài)HPS上(shàng)以(yǐ)800000 MHz的(de)頻率拍攝了(le)9680个(gè)周期(qī)，10个(gè)图(tú)像的(de)k值为(wèi)10，而(ér)FPGA在(zài)相同(tóng)的(de)测試中(zhōng)花費了(le)20个(gè)周期(qī)但是(shì)在(zài)FPGA的(de)50000 MHz时(shí)鐘(zhōng)。運行100个(gè)图(tú)像时(shí)，HPS的(de)周期(qī)數呈指數增长，达(dá)到(dào)6500000个(gè)周期(qī)，而(ér)FPGA需要(yào)110个(gè)周期(qī)。換句(jù)話(huà)说(shuō)，當FPGA線(xiàn)性(xìng)增加时(shí)，我(wǒ)们(men)看(kàn)到(dào)HPS的(de)計(jì)算时(shí)間(jiān)呈指數增长。

图(tú)：分(fēn)類(lèi)器速度(dù)

在(zài)準确性(xìng)方(fāng)面(miàn)，模型按預期(qī)執行。換句(jù)話(huà)说(shuō)，準确度(dù)会(huì)根(gēn)據(jù)您訓練模型的(de)程度(dù)呈指數級增长。我(wǒ)们(men)設計(jì)的(de)第(dì)一(yī)次(cì)叠代(dài)允许存儲最(zuì)多(duō)100个(gè)图(tú)像。对(duì)于(yú)面(miàn)部(bù)識别，我(wǒ)们(men)看(kàn)到(dào)假設背景图(tú)像保持(chí)相对(duì)相似，每张(zhāng)脸約有(yǒu)25张(zhāng)图(tú)像保證接近(jìn)完美的(de)結果(guǒ)。最(zuì)終(zhōng)編譯的(de)設計(jì)最(zuì)多(duō)允许存儲300个(gè)模型，这(zhè)樣(yàng)可(kě)以(yǐ)獲得更(gèng)高(gāo)的(de)精度(dù)。作为(wèi)基準，似乎每个(gè)分(fēn)類(lèi)至(zhì)少(shǎo)保存了(le)25个(gè)图(tú)像，準确率达(dá)到(dào)99％左(zuǒ)右(yòu)。

图(tú)：分(fēn)類(lèi)器的(de)準确性(xìng)

除了(le)遵循一(yī)般正(zhèng)确的(de)編碼程序以(yǐ)确保沒(méi)有(yǒu)意(yì)外(wài)或(huò)未定(dìng)義的(de)行为(wèi)之外(wài)，确实沒(méi)有(yǒu)安(ān)全(quán)考慮因(yīn)素。在(zài)使用(yòng)方(fāng)面(miàn)，我(wǒ)们(men)看(kàn)到(dào)用(yòng)戶界面(miàn)相对(duì)容易遵循。我(wǒ)们(men)讓Key 3捕獲了(le)一(yī)个(gè)新图(tú)像，并将标(biāo)签(qiān)分(fēn)配为(wèi)Switch 6，Switch 5，Switch 4. Key 2将嘗試对(duì)新的(de)图(tú)像捕獲進(jìn)行分(fēn)類(lèi)。并且Key 0充當重(zhòng)置。我(wǒ)们(men)有(yǒu)很多(duō)同(tóng)行嘗試我(wǒ)们(men)的(de)項目，所(suǒ)有(yǒu)人(rén)都回(huí)答(dá)说(shuō)它(tā)非(fēi)常直(zhí)观。

分(fēn)類(lèi)：

距離計(jì)算器的(de)原始設計(jì)包(bāo)括12周期(qī)流水(shuǐ)線(xiàn)距離計(jì)算。这(zhè)是(shì)为(wèi)了(le)防止大型扇(shàn)出(chū)实例化(huà)64个(gè)減法器和(hé)60个(gè)加法器，并将这(zhè)些減法器連(lián)接起来(lái)進(jìn)行1个(gè)周期(qī)的(de)計(jì)算。最(zuì)初的(de)設計(jì)有(yǒu)一(yī)个(gè)稍微複雜的(de)管(guǎn)道(dào)，其中(zhōng)12个(gè)循环(huán)流水(shuǐ)線(xiàn)距離計(jì)算器将被(bèi)实例化(huà)，并且将有(yǒu)一(yī)个(gè)仲裁器用(yòng)于(yú)決定(dìng)在(zài)每个(gè)周期(qī)使用(yòng)哪个(gè)距離計(jì)算器。最(zuì)終(zhōng)，这(zhè)两(liǎng)種(zhǒng)設計(jì)将導致(zhì)類(lèi)似的(de)吞吐量(liàng)（假設具有(yǒu)相同(tóng)的(de)并行化(huà)水(shuǐ)平），同(tóng)时(shí)节(jié)省(shěng)了(le)幾(jǐ)个(gè)潛在(zài)的(de)加法器，并且還(huán)大幅減少(shǎo)了(le)扇(shàn)出(chū)。然而(ér)，二(èr)次(cì)設計(jì)最(zuì)終(zhōng)證明(míng)要(yào)好(hǎo)得多(duō)。

分(fēn)揀機(jī)和(hé)選擇器：

分(fēn)揀機(jī)和(hé)選擇器都經(jīng)曆了(le)多(duō)次(cì)叠代(dài)。最(zuì)棘手(shǒu)的(de)部(bù)分(fēn)是(shì)平衡單周期(qī)分(fēn)揀機(jī)的(de)複雜性(xìng)，并保持(chí)設計(jì)“輕(qīng)量(liàng)化(huà)”以(yǐ)保護ALM，以(yǐ)防項目其他(tā)部(bù)分(fēn)需要(yào)它(tā)们(men)。分(fēn)揀機(jī)桶(tǒng)模块(kuài)的(de)许多(duō)叠代(dài)具有(yǒu)来(lái)自(zì)其他(tā)桶(tǒng)的(de)更(gèng)多(duō)輸入(rù)并且包(bāo)含多(duō)个(gè)寄存器。在(zài)設計(jì)中(zhōng)使用(yòng)寄存器總(zǒng)是(shì)增加了(le)必要(yào)周期(qī)的(de)數量(liàng)，并使設計(jì)更(gèng)加複雜。排序的(de)最(zuì)終(zhōng)解(jiě)決方(fāng)案(àn)非(fēi)常优雅，并且盡可(kě)能(néng)少(shǎo)地(dì)使用(yòng)铲斗(dǒu)模块(kuài)之間(jiān)的(de)互連(lián)。選擇器的(de)設計(jì)較少(shǎo)涉及(jí)，但是(shì)，由(yóu)于(yú)Verilolg中(zhōng)叠代(dài)器的(de)繁瑣性(xìng)，需要(yào)花費相當多(duō)的(de)时(shí)間(jiān)来(lái)测試。作为(wèi)测試選擇器模块(kuài)的(de)一(yī)部(bù)分(fēn)，我(wǒ)们(men)檢查了(le)前(qián)幾(jǐ)个(gè)k的(de)數量(liàng)鄰居與(yǔ)所(suǒ)選結果(guǒ)相匹(pǐ)配。我(wǒ)们(men)決定(dìng)将这(zhè)些信(xìn)息保存为(wèi)我(wǒ)们(men)向(xiàng)用(yòng)戶“冒泡”的(de)內(nèi)容，以(yǐ)查看(kàn)匹(pǐ)配的(de)接近(jìn)程度(dù)，并可(kě)能(néng)決定(dìng)是(shì)否需要(yào)更(gèng)多(duō)地(dì)訓練算法。

由(yóu)此(cǐ)産生(shēng)的(de)分(fēn)類(lèi)和(hé)選擇設計(jì)在(zài)硬(yìng)件(jiàn)上(shàng)遠(yuǎn)遠(yuǎn)快(kuài)于(yú)其软(ruǎn)件(jiàn)对(duì)應(yìng)物(wù)。即使是(shì)最(zuì)好(hǎo)的(de)排序算法也(yě)具有(yǒu)複雜度(dù)O（nlogn），而(ér)我(wǒ)们(men)的(de)最(zuì)差情(qíng)況时(shí)序恰好(hǎo)为(wèi)n。排序在(zài)n个(gè)循环(huán)中(zhōng)完成(chéng)，其中(zhōng)n是(shì)訓練集的(de)大小。關(guān)于(yú)分(fēn)類(lèi)图(tú)像的(de)決定(dìng)是(shì)在(zài)k + 1个(gè)循环(huán)中(zhōng)达(dá)到(dào)的(de)，其中(zhōng)k是(shì)所(suǒ)選擇的(de)最(zuì)近(jìn)鄰居的(de)數量(liàng)。

結論

評論：

在(zài)我(wǒ)们(men)的(de)項目中(zhōng)，我(wǒ)们(men)開(kāi)始在(zài)FPGA上(shàng)構建kNN算法，以(yǐ)展(zhǎn)示硬(yìng)件(jiàn)加速如(rú)何幫助機(jī)器学習算法实現(xiàn)僅使用(yòng)软(ruǎn)件(jiàn)无法找(zhǎo)到(dào)的(de)速度(dù)。我(wǒ)们(men)發(fà)現(xiàn)我(wǒ)们(men)的(de)硬(yìng)件(jiàn)实現(xiàn)明(míng)顯快(kuài)于(yú)我(wǒ)们(men)的(de)软(ruǎn)件(jiàn)实現(xiàn)，这(zhè)與(yǔ)我(wǒ)们(men)期(qī)望看(kàn)到(dào)的(de)結果(guǒ)相匹(pǐ)配。我(wǒ)们(men)還(huán)試图(tú)在(zài)識别器上(shàng)实現(xiàn)合理的(de)準确性(xìng)，并且只(zhī)要(yào)对(duì)象(xiàng)的(de)背景類(lèi)似于(yú)之前(qián)看(kàn)到(dào)的(de)那(nà)个(gè)，分(fēn)類(lèi)器就(jiù)非(fēi)常準确。該設備在(zài)嘗試在(zài)全(quán)新背景中(zhōng)找(zhǎo)到(dào)已經(jīng)分(fēn)類(lèi)的(de)对(duì)象(xiàng)时(shí)不(bù)是(shì)最(zuì)有(yǒu)效的(de)，但如(rú)果(guǒ)它(tā)被(bèi)用(yòng)作縱向(xiàng)分(fēn)析器，例如(rú)在(zài)完全(quán)白色(sè)的(de)背景上(shàng)，則可(kě)以(yǐ)可(kě)靠地(dì)正(zhèng)确地(dì)对(duì)图(tú)像進(jìn)行分(fēn)類(lèi)。如(rú)果(guǒ)我(wǒ)们(men)要(yào)重(zhòng)做項目，我(wǒ)们(men)可(kě)能(néng)会(huì)尋找(zhǎo)其他(tā)方(fāng)法来(lái)專門(mén)化(huà)項目，例如(rú)，将图(tú)像存儲在(zài)硬(yìng)件(jiàn)上(shàng)，以(yǐ)便我(wǒ)们(men)可(kě)以(yǐ)執行複雜的(de)數学運算，例如(rú)梯(tī)度(dù)分(fēn)析，以(yǐ)便对(duì)面(miàn)部(bù)進(jìn)行分(fēn)類(lèi)。然而(ér)，这(zhè)種(zhǒng)專業化(huà)将以(yǐ)功能(néng)或(huò)空間(jiān)为(wèi)代(dài)價，因(yīn)为(wèi)我(wǒ)们(men)用(yòng)于(yú)合理規模的(de)項目实施的(de)開(kāi)發(fà)板上(shàng)幾(jǐ)乎沒(méi)有(yǒu)足够的(de)空間(jiān)。