Fungsi carian sedang dalam pembinaan.
Fungsi carian sedang dalam pembinaan.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Open Access
High-Throughput Exact Matching Implementation on FPGA with Shared Rule Tables among Parallel Pipelines
Membuka akses
Pelaksanaan Pemadanan Tepat Tembus Tinggi pada FPGA dengan Jadual Peraturan Dikongsi antara Talian Paip Selari

Xiaoyong SONG, Zhichuan GUO, Xinshuo WANG, Mangu SONG

  • pandangan teks lengkap

    365

  • Petikan Ini
  • Free PDF (2.2MB)

Ringkasan:

Dalam rangkaian takrifan perisian (SDN), pemprosesan paket lazimnya dilaksanakan menggunakan model tindakan padanan, di mana paket diproses berdasarkan tindakan dipadankan dalam jadual tindakan padanan. Disebabkan oleh sumber on-board FPGA yang terhad, ia merupakan satu cabaran penting untuk mencapai daya pemprosesan tinggi berskala besar berdasarkan padanan tepat (EM), sambil menyelesaikan konflik cincang dan masalah luar pesanan. Untuk menangani isu ini, kajian ini mencadangkan jadual EM berasaskan FPGA yang memanfaatkan jadual peraturan dikongsi merentas berbilang saluran paip untuk menghapuskan replikasi memori dan meningkatkan daya pemprosesan keseluruhan. Fungsi penyusunan semula yang tidak tertib digunakan untuk memastikan penjujukan paket dalam saluran paip. Selain itu, untuk mengendalikan perlanggaran dan meningkatkan faktor beban jadual cincang, berbilang blok jadual cincang digabungkan dan jadual EM berasaskan CAM tambahan disepadukan dalam setiap saluran paip. Untuk pengetahuan terbaik kami, ini adalah kali pertama reka bentuk yang dicadangkan mempertimbangkan pemulihan operasi yang tidak mengikut pesanan dalam jadual EM berbilang saluran untuk aplikasi pemprosesan paket rangkaian berkelajuan tinggi. Tambahan pula, ia dilaksanakan pada tatasusunan get boleh atur medan Xilinx Alveo U250, yang mempunyai sejuta peraturan dan mencapai kelajuan pemprosesan sebanyak 200 juta operasi sesaat, secara teorinya membolehkan daya pemprosesan melebihi 100 Gbps untuk paket saiz 64-Byte.

Jawatankuasa
IEICE TRANSACTIONS on Communications Vol.E107-B No.5 pp.387-397
Tarikh penerbitan
2024/05/01
Diumumkan
ISSN dalam talian
1745-1345
DOI
10.23919/transcom.2023EBP3140
Jenis Manuskrip
PAPER
kategori
Sistem Rangkaian

1. Pengenalan

Dalam rangkaian takrifan perisian (SDN), kebanyakan fungsi rangkaian dilaksanakan berdasarkan model jadual tindakan padanan (MAT). Dalam MAT, medan khusus paket data diekstrak sebagai kunci untuk menyiasat jadual padanan, dan arahan tindakan yang harus dilaksanakan diperoleh selepas padanan yang berjaya [1], [2]. Jadual padanan tepat (EM) memainkan peranan penting dan digunakan secara meluas dalam aplikasi pemprosesan paket seperti pemeriksaan paket [3], pengelasan paket [4] dan pemantauan aliran [5] dsb. Kelajuan pemprosesan paket rangkaian dan skala rangkaian meningkat secara berterusan, bersama-sama dengan keperluan prestasi pemprosesan yang lebih tinggi untuk peranti suis, yang juga menuntut prestasi dan kebolehskalaan yang lebih tinggi kepada jadual padanan yang tepat.

Tatasusunan gerbang boleh atur cara lapangan (FPGA) mempunyai kelebihan yang ketara dari segi fleksibiliti boleh atur cara dan pemprosesan selari, dan pelbagai fungsi rangkaian sedang dipunggah ke FPGA untuk pemprosesan dipercepatkan [6]. Walau bagaimanapun, EM mahupun memori boleh alamat kandungan (CAM) tidak ada pada FPGA. Pengguna perlu mereka bentuk dan melaksanakan jadual padanan berdasarkan sumber on-board. Pada FPGA, kaedah utama untuk melaksanakan jadual padanan tepat termasuk kaedah berasaskan cincang dan kaedah berasaskan CAM. Jadual padanan tepat berdasarkan CAM menggunakan sumber yang besar dan mempunyai kecekapan ingatan yang rendah [7]. Jadual EM berdasarkan cincang mempunyai kecekapan ingatan yang lebih tinggi, tetapi terdapat masalah seperti perlanggaran cincang, kesukaran memasukkan, dan kependaman kes terburuk tidak tentu [8], [9]. Selain itu, kedua-dua kaedah akan menghadapi kesukaran untuk mencapai kedalaman besar atau lebar besar EM pada FPGA dengan kelajuan tinggi.

Untuk meningkatkan daya pemprosesan jadual padanan, sesetengah reka bentuk menggunakan berbilang saluran selari. Walau bagaimanapun, ia juga membawa masalah replikasi memori [10], mengakibatkan penggunaan storan pada cip yang besar. Sesetengah reka bentuk berbilang saluran [11], [12] tanpa replikasi storan juga mempunyai masalah faktor beban jadual hash yang rendah. Selain itu, berbeza daripada pelaksanaan luar perintah Sistem Nilai Kunci (KVS) umum dalam pangkalan data, adalah perlu untuk mengekalkan susunan urutan paket dalam kebanyakan aplikasi pemprosesan paket rangkaian. Oleh itu, isu kependaman pemprosesan yang tidak menentu atau paket yang tidak teratur juga harus dipertimbangkan dalam aplikasi jadual pemadanan rangkaian.

Untuk melaksanakan jadual pemadanan tepat pemprosesan tinggi berskala besar dan menyelesaikan masalah perlanggaran pencincangan dan tersusun di kalangan berbilang saluran paip, kertas kerja ini mencadangkan jadual pemadanan tepat berbilang saluran dengan jadual peraturan dikongsi, yang boleh meningkatkan kelajuan pemprosesan daripada jadual padanan tanpa replikasi memori. Terutamanya, ia akan menyusun semula keputusan padanan yang tidak tertib selepas diproses untuk memastikan urutan yang betul, yang mengelakkan paket tersusun atau ralat dalam rangkaian. Sumbangan utama kerja ini adalah seperti berikut:

  • Kertas kerja ini mencadangkan pelaksanaan padanan tepat berasaskan FPGA yang memanfaatkan jadual peraturan dikongsi merentas saluran paip selari untuk meningkatkan daya pemprosesan keseluruhan tanpa replikasi memori. Jadual EM yang dilaksanakan berdasarkan FPGA boleh memasukkan sejuta peraturan, yang mempunyai kebolehskalaan yang baik dan mencapai kelajuan pemprosesan 200 juta operasi sesaat, secara teorinya membolehkan daya pemprosesan melebihi 100 Gbps untuk paket saiz 64-Byte.
  • Fungsi penyusunan semula yang tidak tertib untuk memulihkan tertib keputusan padanan dalam saluran paip untuk mengekalkan urutan paket dalam pemprosesan paket rangkaian.
  • Jadual padanan tepat berasaskan CAM yang padat digabungkan bersama jadual EM berasaskan cincang utama dalam setiap saluran paip untuk mengendalikan perlanggaran cincang, yang memastikan peraturan penting boleh dimasukkan ke dalam jadual peraturan.

2. Gambaran Keseluruhan Jadual Padanan Tepat

2.1 Model Padanan-Tindakan

Seperti yang ditunjukkan dalam Rajah 1, model aksi padanan ialah rangka kerja arus perdana untuk memproses paket data dalam satah data peranti boleh atur cara. Pada setiap peringkat pemprosesan paket data, padanan ciri yang difailkan dalam paket diekstrak sebagai Utama dan digunakan untuk operasi carian jadual MAT [2], [13]. Enjin tindakan kemudian melaksanakan tindakan berdasarkan hasil carian jadual. Di antara pelbagai jenis jadual MAT yang digunakan dalam pemprosesan paket dan padanan corak, jadual padanan tepat biasanya digunakan.

Rajah 1  Skema asas model aksi perlawanan. (a) Seni bina jadual padanan tepat berasaskan hash. (b) Seni bina jadual padanan tepat berasaskan CAM. (c) Seni bina jadual padanan tepat tanpa perlanggaran.

Terdapat dua cara utama untuk melaksanakan EM pada FPGA, iaitu EM berasaskan hash seperti [10] dan EM berasaskan CAM seperti [14]. Kedua-dua jadual pemadanan tepat berasaskan cincang dan berasaskan CAM mempunyai prestasi carian O(1). Sebaliknya, EM berasaskan hash mempunyai kecekapan penggunaan storan yang lebih tinggi, manakala CAM berasaskan SRAM mempunyai penggunaan storan yang rendah. Walau bagaimanapun, EM berasaskan CAM tidak mempunyai masalah seperti perlanggaran cincang atau kesukaran memasukkan, dsb.

2.2 Jadual Padanan Tepat Berasaskan Hash

Jadual padanan tepat berasaskan cincang yang ditunjukkan dalam Rajah 1(a) ialah struktur data yang pantas dan cekap yang menyimpan Nilai-Kekunci pasangan dalam {Vld, Kunci, Nilai} struktur data dalam setiap ruang alamat. Semasa memasukkan atau bertanya, Utama dicincang untuk menjana indeks alamat yang sepadan, dan kemudian struktur data disimpan di alamat atau diambil untuk perbandingan, akhirnya menghasilkan nilai yang sepadan.

2.3 Jadual Padanan Tepat Berasaskan CAM

Memori Beralamat Kandungan (CAM) ialah sejenis memori yang membolehkan pertanyaan kandungan pantas dan mempunyai kelebihan kadar carian pantas. Seperti Rajah 1(b) yang ditunjukkan, dalam jadual padanan tepat berasaskan CAM, utama dimasukkan ke dalam CAM untuk mendapatkan maklumat yang sepadan garisan perlawanan yang mengandungi semua hasil padanan setiap unit alamat dan indeks alamat padanan dikodkan oleh Pengekod Keutamaan. Akhir sekali, alamat ini digunakan untuk membaca yang sepadan nilai daripada Stor Nilai.

2.4 Jadual Padanan Tepat Tanpa Perlanggaran

Kebarangkalian perlanggaran bergantung pada fungsi cincang, yang tidak mungkin sempurna, terutamanya dalam kes rawak dan data yang kerap dikemas kini [7]. Untuk menyelesaikan konflik cincang, cincang cuckoo [9], jadual cincang berbilang peringkat [10] atau rantaian [15], menambah storan tambahan [5], [12], [16] dan penyelesaian lain telah dicadangkan. Rajah 1(c) menunjukkan jadual padanan tepat tanpa perlanggaran digabungkan dengan EM berasaskan cincang dan EM berasaskan CAM. Entri peraturan mula-mula dimasukkan ke dalam jadual EM berasaskan cincang. Jika perlanggaran berlaku, entri bercanggah kemudiannya dimasukkan ke dalam jadual EM berasaskan CAM. Struktur hibrid ini memanfaatkan faedah kedua-dua CAM dan teknik berasaskan cincang untuk memastikan padanan yang cekap dan bebas perlanggaran.

3. Seni bina

Walaupun jadual cincang mempunyai kebolehskalaan yang baik dan penggunaan sumber yang tinggi, melaksanakan jadual EM berprestasi tinggi pada FPGA masih menjadi cabaran, terutamanya apabila saiz jadual adalah besar. Sukar untuk melakukan pemadanan dengan daya pemprosesan yang mencukupi untuk pemprosesan kelajuan wayar. Sebagai contoh, dalam rangkaian berkelajuan tinggi 100 Gbps, sekurang-kurangnya 148.8 juta paket saiz 64B sesaat mesti diproses untuk memenuhi keperluan kelajuan pemprosesan, yang bermaksud daya pemprosesan operasi jadual padanan tidak boleh lebih rendah daripada 148.8 juta.

Idea teras untuk meningkatkan kelajuan pemprosesan adalah untuk memaksimumkan bilangan operasi yang diproses setiap kitaran jam. Biasanya, kelajuan pemprosesan ditingkatkan dengan meningkatkan frekuensi utama sistem atau penggunaan pelbagai saluran paip selari [17]. Tidak mudah untuk menambah baik frekuensi pada FPGA, terutamanya apabila keseluruhan sistem adalah kompleks dan saiz jadual adalah besar. Masalah yang dihadapi oleh berbilang saluran paip selari ialah ia memerlukan memori berbilang port atau replikasi memori untuk menyimpan setiap peraturan beberapa kali, yang menggunakan lebih banyak sumber storan. Oleh kerana sumber yang terhad pada FPGA, kaedah replikasi ingatan tidak boleh digunakan apabila melaksanakan jadual padanan skala yang sangat besar.

3.1 Jadual Hash Dikongsi Selari dengan Struktur CAM

Untuk mengelakkan replikasi storan dan meningkatkan bilangan entri yang diproses dalam satu kitaran jam, kami mengoptimumkan struktur saluran paip cincang berbilang peringkat kepada struktur saluran paip selari berbilang. Selain itu, berbilang jadual CAM telah diterima pakai untuk mengendalikan percanggahan cincang.

Semua saluran paip berkongsi semua peraturan yang disimpan dalam keseluruhan jadual padanan tepat, dan setiap peraturan hanya disimpan sekali sahaja tanpa sandaran. Jadual dalam setiap saluran paip boleh diakses oleh operasi dari saluran paip jirannya jika perlu. Bagi setiap kunci, terdapat kebarangkalian bahawa ia akan dimasukkan atau dipadankan dalam set jadual cincang bagi setiap saluran paip. Jika operasi berjaya dalam set jadual cincang, tidak perlu mengakses jadual lain dalam saluran paip lain. Sementara itu, jadual dalam saluran paip lain boleh memproses operasi lain. Dalam senario terburuk, apabila semua jadual EM dalam semua saluran paip perlu diakses untuk setiap kunci, daya pemprosesan keseluruhan jadual EM adalah sama seperti saluran paip tunggal. Dalam senario terbaik, semua operasi berjaya dalam set jadual cincang pertama yang mereka akses, dan keseluruhan jadual padanan tepat boleh mengendalikan P operasi dalam setiap kitaran jam. Walau bagaimanapun, bagi kebanyakan kes, \(1\leq p\leq P\), Di mana p ialah bilangan operasi yang boleh diproses oleh EM dalam kitaran jam dan P ialah bilangan saluran paip.

Dalam keseluruhan jadual EM, terdapat P saluran paip selari, setiap satu terdiri daripada satu set blok jadual cincang sebagai storan utama dan jadual EM berasaskan CAM sebagai storan tambahan. Rajah 2 menunjukkan seni bina jadual EM kami dengan empat saluran paip selari. Berbilang fungsi cincang dan blok jadual cincang digunakan dalam setiap set jadual cincang untuk mengurangkan kadar perlanggaran cincang. Untuk mengelakkan ketidakpastian dalam masa pemasukan yang disebabkan oleh pencincangan cuckoo, kami memilih ruang alamat kosong daripada berbilang alamat alternatif secara selari, dan entri baharu yang bercanggah akan dimasukkan dalam set jadual cincang lain dan bukannya menggantikan entri sedia ada jika tiada alamat alternatif kosong dalam set jadual cincang semasa. Entri gagal dimasukkan ke dalam semua jadual cincang akhirnya dimasukkan ke dalam CAM. Untuk mengekalkan urutan paket dan memastikan kependaman carian yang berterusan, terdapat a Menyusun semula modul di belakang set jadual cincang dan jadual CAM untuk mengembalikan kunci yang dicari dan hasil yang dipadankan ke saluran paip inputnya sendiri, dan menyatukan kependaman setiap kunci carian mengikut laluan operasinya.

Rajah 2  Keseluruhan seni bina jadual tepat dengan 4 saluran paip selari.

3.2 Blok Jadual Hash dan Set Jadual Hash

Dalam setiap saluran paip, terdapat satu set blok jadual EM berasaskan cincang, di sini dipanggil set jadual hash. Setiap set jadual hash terdiri daripada M blok jadual cincang, dan blok jadual cincang ini bebas dan simpan Nilai-Kekunci pasangan dalam unit alamat mereka dengan struktur kemasukan {Vld, Kunci, Nilai}. Jika Vld ialah '1', ia menunjukkan struktur kemasukan adalah sah dan slot dalam blok jadual cincang telah digunakan.

3.2.1 Kelas H3 Fungsi Hash

Prestasi skim pencincangan bergantung pada kaedah pengendalian perlanggaran dan fungsi pencincangan yang dipilih [18].

Kelas H3 algoritma cincang [8] digunakan untuk melaksanakan operasi pencincangan pada kunci, yang telah ditunjukkan berkesan untuk mengedarkan kunci secara rawak [10]. biarlah i menandakan bilangan bit untuk kunci input, dan j menandakan bilangan bit untuk indeks hash. biarlah Q menandakan a \(i\times j\) Matriks Boolean. Untuk diberikan \(q \in \) Q, biarkan q(m) menjadi rentetan bit daripada mbaris ke Q, dan biarkan x(m) menandakan mkekunci input ke. Fungsi pencincangan \(h(x):A \rightarrow B\) ditakrifkan sebagai

\[\begin{equation*} h(x) =(x(1)\cdot q(1))\oplus(x(2)\cdot q(2))\oplus\ldots\oplus(x(i)\cdot q(i)). \tag{1} \end{equation*}\]

Berbanding dengan algoritma pencincangan lain seperti Toeplitz [19], yang H3 algoritma bukan sahaja memastikan keseragaman dan pengiraan pantas tetapi juga menggunakan sumber logik yang lebih sedikit apabila dilaksanakan pada FPGA. Perkakasan yang menyimpan H3 matriks boleh dianjurkan dalam bank daftar. Perkakasan yang sama boleh merealisasikan sebarang fungsi pencincangan yang dikehendaki dari kelas ini dan fungsi pencincangan boleh diubah secara dinamik dengan memuatkan data ke dalam bank daftar jika diperlukan [18]. Untuk menambah baik kekerapan jam, operasi pencincangan disalurkan dan diselesaikan dalam dua kitaran jam.

3.2.2 Pengendalian Perlanggaran Hash

Untuk mengurangkan perlanggaran cincang, bebas H3 matriks cincang ditetapkan untuk setiap blok jadual cincang, dan keseluruhan jadual EM mempunyai \(P\times M\) H3 matriks cincang dan \(P\times M\) unit fungsi hash. Jika perlanggaran cincang berlaku semasa pemasukan, entri baharu akan memilih slot kosong lain untuk dimasukkan, bukannya menggantikan entri asal seperti pencincangan cuckoo. Dalam setiap set jadual hash, M unit fungsi cincang melakukan pengiraan cincang pada kekunci yang sama secara selari, dan kemudian pilih alamat tanpa konflik cincang daripada M alamat calon untuk dimasukkan. Dengan peningkatan bilangan blok jadual cincang dalam setiap set jadual cincang, kadar perlanggaran cincang akan dikurangkan dengan ketara, yang akan diterangkan lebih lanjut dalam Sekt. 4.1. Jika tiada alamat calon kosong dalam set jadual cincang semasa, operasi sisipan diteruskan ke set jadual cincang saluran paip seterusnya. Jika semua jadual cincang gagal disisipkan, entri yang bercanggah disimpan dalam jadual CAM akhirnya.

3.2.3 Operasi
  • Memasukkan: Seperti yang digambarkan dalam Rajah 3, untuk setiap set jadual cincang, M unit fungsi cincang dalam set ini mula-mula menjana M alamat calon untuk kunci semasa memasukkan kemasukan. Kemudian struktur kemasukan yang disimpan dalam alamat calon setiap blok jadual hash dibaca. Sekiranya Vld bit dalam struktur kemasukan ialah '0', alamatnya kosong, dan '1' menunjukkan bahawa ruang alamat ini telah pun digunakan. The Logik pengendalian perlanggaran memilih blok jadual cincang dengan alamat calon kosong untuk disisipkan. Tulis logik menulis struktur kemasukan entri baharu ke dalam alamat sepadan jadual yang dipilih.

Rajah 3  Proses masukkan set jadual hash.

  • Query: Seperti yang digambarkan dalam Rajah 4, selepas pengiraan pencincangan dan bacaan struktur kemasukan, kunci yang ditanya dibandingkan dengan semua kunci dalam struktur kemasukan yang sah. Selepas membandingkan, Bandingkan logik mengekod semua hasil perbandingan dan mendapatkan alamat yang sepadan, dan kemudian nilai yang sepadan dipilih mengikut alamat yang sepadan.
  • Padam: Melakukan operasi pertanyaan terlebih dahulu. Selepas pemadanan berjaya, kandungan alamat yang sepadan ditulis kepada 0 untuk memadamkan entri.

Rajah 4  Proses pertanyaan set jadual cincang.

3.3 Jadual CAM Bantu

Walaupun kita menggunakan berbilang fungsi cincang dan berbilang blok jadual cincang untuk mengurangkan kebarangkalian perlanggaran cincang, fungsi cincang yang sempurna tidak wujud. Untuk mengelakkan situasi di mana peraturan penting tidak boleh dimasukkan ke dalam jadual cincang disebabkan oleh konflik cincang, kami menangani masalah ini dengan menambahkan storan tambahan, iaitu jadual EM berasaskan CAM kedalaman kecil untuk menyimpan entri yang tidak boleh dimasukkan ke dalam jadual cincang.

CAM di sini dilaksanakan menggunakan kaedah SRAM transpos [20]. Dalam pelaksanaan kaedah ini, kunci digunakan sebagai alamat tulis atau baca, dan garisan perlawanan mengandungi maklumat alamat kemasukan disimpan dalam SRAM. Lebar daripada garisan perlawanan adalah sama dengan kedalaman CAM, dengan setiap ruang alamat sepadan dengan satu bit masuk garisan perlawanan. Untuk kunci yang diberikan, jika bit tertentu dalam sepadannya garisan perlawanan ialah '1', ini bermakna alamat tersebut ialah alamat yang sepadan.

Secara teorinya, kedalaman CAM bergantung pada kebarangkalian perlanggaran cincang, dan analisis terperinci akan disediakan dalam Sekt. 4.2. Di sini, kami menganggap bahawa jumlah keperluan kedalaman CAM ialah \(C_{depth}\). Rajah 5 menggambarkan garis masa operasi dalam jadual EM. Apabila kunci K memasuki jadual padanan, ia akan muncul dalam garis masa dan grid dalam Rajah 5. Grid putih menunjukkan bahawa operasi K belum selesai lagi, dan ia perlu terus memasuki set jadual cincang atau jadual CAM seterusnya untuk mencuba operasinya dengan susunan gelung \(\textit{Pipe}\ 0 \rightarrow \textit{Pipe}\ 1 \rightarrow \textit{Pipe}\ 2 \rightarrow \textit{Pipe}\ 3 \rightarrow \textit{Pipe}\ 0\). Grid hijau menunjukkan bahawa operasi bagi K telah berjaya disiapkan atau semua jadual telah diakses. Untuk setiap kunci, jika operasinya gagal dalam semua jadual cincang, ia akan terus masuk ke dalam jadual CAM. Kunci gagal melakukan operasi dalam jadual CAM akan mengakses jadual CAM seterusnya dengan susunan gelung yang sama \(\textit{CAM}\ 0 \rightarrow \textit{CAM}\ 1 \rightarrow \textit{CAM}\ 2 \rightarrow \textit{CAM}\ 3 \rightarrow \textit{CAM}\ 0\). Sebagai contoh, operasi bagi K1 gagal dalam semua set jadual cincang dan akhirnya ia menyelesaikan operasinya dalam jadual CAM 0. Untuk mengelakkan senario kes terburuk yang ditunjukkan dalam Rajah 5, apabila semua set jadual cincang dalam berbilang saluran paip perlu memasukkan entri bercanggah ke dalam CAM secara serentak (K10, K11, K12, dan K13), kami meletakkan jadual CAM selepas setiap set jadual hash dalam setiap saluran paip. Kunci daripada K10, K11, K12, dan K13 gagal melakukan operasi mereka selepas merentasi semua jadual cincang dalam empat saluran paip. Selepas modul Susun Semula pertama di belakang jadual cincang dalam Rajah 2, K10 \(\sim\) K13 masukkan ke dalam jadual CAM dengan saluran paip yang sepadan. Kedalaman CAM dalam setiap saluran paip \(CD = \frac{C_{depth}}{P}\), Di mana P ialah bilangan saluran paip atau bilangan set jadual cincang.

Rajah 5  Garis masa operasi (H: Set Jadual Hash. C: Jadual CAM. K: Kekunci Operasi. H0, H1, H2, H3 ialah empat set jadual hash dalam Rajah 2, dan C0, C1, C2, C3 ialah empat Jadual CAM dalam Rajah 2. K0, K1, \(\cdots\), K13 ialah kunci operasi ke dalam jadual).

Dengan menggabungkan jadual EM berasaskan CAM dengan jadual EM berasaskan cincang, ia boleh menangani potensi konflik cincang dan memastikan peraturan penting dimasukkan dengan betul ke dalam jadual padanan.

3.3.1 Pengurusan Ruang Alamat

Seperti yang ditunjukkan dalam Rajah 6, untuk setiap jadual CAM terdapat peta bit CAM Vld vektor yang merekodkan status penggunaan setiap ruang alamat CAM. '0' bermakna ruang sudah digunakan, manakala '1' bermaksud ruang itu tersedia untuk digunakan. Apabila memasukkan entri ke dalam CAM, penjana indeks alamat memperuntukkan ruang alamat kosong kepada entri ini dengan vld bitmap dan pengekod keutamaan. Selepas entri dipadamkan, alamat yang sepadan vld bit yang sepadan akan ditetapkan kepada '1' sekali lagi, menunjukkan alamat ini boleh diagihkan semula.

Rajah 6  Seni bina jadual EM berasaskan CAM.

3.3.2 Operasi
  • Memasukkan: Selepas menjana indeks tulis, the kandungan baru entri dijana berdasarkan indeks tulis (\(new\ content = 1 << write\ index\)). Pada masa yang sama, kandungan asal dalam alamat kunci penulisan hendaklah dibaca sebagai matchiline lama. Yang kandungan baru and matchiline lama melaksanakan or operasi untuk menjana matchiline baru ditulis ke dalam CAM. Matchiline baru = garis mancis lama | kandungan baharu. Gunakan kekunci entri sebagai alamat tulis, tulis ini matchiline baru ke dalam CAM. Pada masa yang sama, tulis nilai yang sepadan ke dalam stor nilai pada indeks tulis. Tetapkan bit yang sepadan dalam vld bitmap kepada '0' untuk menunjukkan alamat sedang digunakan.
  • Query: Semasa pertanyaan, kunci digunakan sebagai alamat baca untuk membaca garisan perlawanan disimpan dalam CAM. Pengekod keutamaan digunakan untuk mengekod garisan perlawanan dan dapatkan indeks padanan. Jika ruang alamat sedang digunakan, baca nilai sepadan yang disimpan dalam ruang alamat ini daripada stor nilai.
  • Padam: Selepas menyelesaikan operasi pertanyaan, kosongkan kandungan bit yang sepadan dalam garisan padanan di alamat kunci dalam CAM dan juga kosongkan kandungan pada indeks yang sepadan bagi stor nilai. Tetapkan bit yang sepadan dalam bitmap kepada '1', menunjukkan bahawa ia boleh digunakan semula.
3.4 Nyatakan Struktur Merentasi Talian Paip

Selain struktur kemasukan yang disimpan dalam jadual EM, struktur data tersuai dikekalkan dan dipindahkan antara saluran paip untuk merekodkan status dan laluan data setiap operasi, di sini kami memanggilnya struktur negeri. Seperti yang ditunjukkan dalam Rajah 7, struktur keadaan ini mempunyai panjang 8 bit, dan setiap sub-medan ditakrifkan seperti berikut:

Rajah 7  Struktur negeri merentasi saluran paip EM.

  • [0]: Berjaya - Menunjukkan sama ada pengendalian sesuatu entri berjaya. Ia ditetapkan kepada 1 jika entri telah berjaya dimasukkan atau jika pertanyaan telah berjaya.
  • [2:1]: Kod Pilihan - Nyatakan operasi yang akan dilakukan pada entri ini. 2'b00 menunjukkan tiada operasi, 2'b01 menunjukkan sisipan, 2'b10 menunjukkan pemadaman dan 2'b11 menunjukkan pertanyaan.
  • [6:3]: Keadaan Saluran Paip - Peta bit 4-bit mewakili status sama ada saluran paip atau jadual telah diakses. 1'b0 menunjukkan bahawa jadual telah diakses, dan 1'b1 menunjukkan bahawa jadual belum diakses. Sebagai contoh, 4'b1011 menunjukkan bahawa entri dimasukkan daripada Paip 2 dan jadual masuk Paip 2 telah diakses. Jika akses lanjut diperlukan, langkah seterusnya ialah melompat ke \(\textit{Pipe}\ 3 \rightarrow \textit{Pipe}\ 0 \rightarrow \textit{Pipe}\ 1\) untuk akses sehingga beroperasi berjaya atau semua saluran paip telah diakses. Untuk entri jadual yang tidak berjaya dikendalikan dalam jadual cincang, medan ini akan dipulihkan kepada keadaan awalnya 4'b1111 sebelum memasuki jadual CAM.
  • [7]: Kepada CAM - Menentukan sama ada untuk memasukkan entri ke dalam CAM apabila pemasukan gagal dalam semua jadual cincang. 1'b0 bermakna entri boleh terus dibuang apabila sisipan gagal dalam jadual cincang, manakala 1'b1 bermakna entri masih perlu dimasukkan ke dalam CAM jika perlu.

Sebagai kunci ditanya atau a Nilai-Kekunci dimasukkan ke dalam EM, jadual cincang atau jadual CAM melaksanakan operasi berdasarkannya Kod Pilihan. Jika saluran paip semasa berjaya dilaksanakan, ia terus melompat keluar dari jadual dan memasuki Menyusun semula modul. Jika tidak, jika terdapat jadual saluran paip lain yang belum diakses mengikut Keadaan Saluran Paip, ia terus melompat ke jadual saluran paip seterusnya untuk operasi yang sepadan.

Sebaik sahaja jadual hash atau jadual CAM setiap saluran paip menyelesaikan operasinya, ia mengubah suai bit yang sepadan dalam Keadaan Saluran Paip daripada saluran paip untuk saluran paip itu dan mengemas kini Berjaya bit berdasarkan kejayaan operasi. Selain itu, Menyusun semula akan mengawal masa keluar setiap kemasukan mengikutnya Keadaan Saluran Paip, yang memastikan kependaman pemprosesan setiap entri adalah sama.

Untuk entri pertanyaan, struktur keadaan disebarkan di sepanjang entri pertanyaan sehingga hasil yang sepadan digunakan. Walau bagaimanapun, apabila memasukkan entri, setelah pemasukan berjaya, struktur tidak akan merambat ke belakang lagi.

3.5 Susun Semula Tidak Tertib

Mengikut reka bentuk sebelumnya, apabila entri melengkapkan operasi pertanyaan dalam set jadual cincang atau jadual CAM, ia akan membawa struktur keadaannya dari jadual untuk membolehkan lebih banyak entri baharu mengakses jadual padanan untuk diproses. Memandangkan setiap entri mungkin tidak perlu mengakses semua set jadual cincang atau jadual CAM, kependaman operasi berbeza dari satu entri ke entri. Ini akan mengakibatkan tersusun dan kesesakan di pelabuhan luar jadual EM. Selain itu, dalam aplikasi pemprosesan paket rangkaian, ia biasanya perlu untuk mengekalkan urutan paket.

Untuk memastikan bahawa urutan paket yang masuk dan keluar saluran paip tidak terganggu, dan kependaman pertanyaan setiap entri adalah konsisten, menyusun semula modul diperkenalkan untuk memulihkan susunan entri yang diproses dan membuat kelewatan yang sepadan untuk setiap entri.

Seperti yang ditunjukkan dalam Rajah 8, terdapat empat saluran dalam menyusun semula modul, dan setiap satu sepadan dengan satu saluran dalam jadual EM. Mengambil jadual cincang sebagai contoh, setiap entri yang ditanya membawa struktur statusnya daripada jadual cincang semasa yang ditetapkan ke dalam menyusun semula modul. The unit penghuraian menghuraikan medan keadaan saluran paipnya untuk mengetahui saluran paip mana entri memasuki jadual padanan dan berapa banyak set jadual cincang yang telah diakses. Modul daripada pilih jalan menghantar hasil yang sepadan kembali ke saluran paip yang dimasukkan. Kemudian kelewatan pilih modul memilih kelewatan tambahan yang sesuai untuk entri ini dan mengeluarkannya daripada outport yang sepadan menyusun semula modul.

Rajah 8  Seni bina susunan semula.

Selepas diproses oleh menyusun semula modul, kependaman pertanyaan setiap entri adalah konsisten dan ia adalah sama dengan kelewatan kes terburuk, dan hasil padanan yang sepadan masih boleh dikembalikan ke saluran paipnya sendiri selepas carian saluran paip silang, yang memastikan urutan paket dalam setiap saluran paip dalam pemprosesan kemudian.

Seperti yang digambarkan dalam Rajah 9, tali pinggang dengan warna yang sama masuk ke dalam jadual secara serentak, dan grid berwarna bermakna kunci telah menyelesaikan operasinya. Sebagai contoh, K1, K2, K3 and K4 semuanya hijau kerana mereka semua masuk ke dalam jadual EM pada kali pertama. K1 menyelesaikan operasinya dalam set jadual pertamanya H0, Tetapi K2, K3 and K4 bukan. Mereka telah melalui 2, 3 dan 4 meja untuk menyelesaikan operasi masing-masing. Kemudian mereka memasuki modul susunan semula dari saluran yang mereka selesaikan operasi. Selepas menyusun semula, empat kekunci ini keluar dari jadual EM secara serentak.

Rajah 9  Garis masa operasi susunan semula.

Kekunci yang dimasukkan dari saluran paip yang sama juga mengekalkan urutannya selepas menyusun semula. K4, K7 and K9 masuk dari H3 set meja pada masa yang berbeza. Walaupun mereka mempunyai kependaman pemprosesan yang berbeza dalam jadual cincang, mereka masih mengekalkan urutannya selepas menyusun semula.

4. Analisis

Di sini kami menganalisis kadar perlanggaran cincang, kapasiti CAM yang diperlukan dan isu konsistensi. Jadual 1 menyenaraikan singkatan pembolehubah yang akan digunakan kemudian dan maknanya.

Jadual 1  Jadual singkatan.

4.1 Kadar Perlanggaran Hash

Terdapat P set jadual cincang dalam keseluruhan jadual EM, dan setiap set jadual cincang mengandungi M blok jadual hash dengan kedalaman HD. Oleh itu, terdapat \(P\times M\) blok jadual hash. Kami mensimulasikan kadar perlanggaran cincang di bawah nombor dan kedalaman blok jadual cincang yang berbeza. Kebarangkalian setiap pencincangan kunci ke lokasi tertentu adalah seragam [21], jadi fungsi rawak seragam bertindak sebagai unit fungsi cincang untuk menjana indeks sisipan dalam simulasi. 1000 eksperimen simulasi telah dijalankan untuk setiap kes dan mengira nilai min. Dalam setiap masa, \(P\times M\times HD\) entri dimasukkan ke dalam jadual cincang.

Keputusan simulasi ditunjukkan dalam Rajah 10. Rajah 10(a) menunjukkan bilangan entri yang berjaya dimasukkan dan Rajah 10(b) menunjukkan bilangan entri yang gagal di bawah nombor jadual yang berbeza dan kedalaman jadual yang berbeza, yang memberikan kita rujukan untuk memilih kedalaman CAM di bawah kes yang berbeza. Ia boleh dilihat daripada Rajah 10(c) dan Rajah 10(d) bahawa dengan pertambahan bilangan blok jadual hash, kadar penggunaan jadual hash (faktor beban) akan meningkat dan kadar perlanggaran akan berkurangan. Apabila bilangan entri yang dimasukkan ke dalam semua jadual cincang adalah sama dengan jumlah ruang alamat dalam jadual cincang, kadar perlanggaran keseluruhan jadual cincang hampir tidak terjejas oleh kedalaman setiap blok jadual cincang, tetapi terutamanya ditentukan oleh bilangan blok jadual hash. Apabila bilangan blok jadual cincang melebihi 64, kadar perlanggaran cincang turun di bawah 1%.

Rajah 10  Hasil simulasi di bawah nombor dan kedalaman blok jadual hash yang berbeza. (a) Bilangan entri yang berjaya dimasukkan ke dalam jadual cincang. (b) Bilangan entri gagal yang tidak dimasukkan ke dalam jadual cincang. (c) Kadar penggunaan keseluruhan jadual cincang. (d) Kadar perlanggaran keseluruhan jadual cincang.

4.2 Kapasiti CAM

Dengan mengandaikan bahawa kadar perlanggaran cincang ialah \(R_{collison}\), Terdapat P set jadual cincang, dan setiap set jadual cincang mempunyai M blok jadual hash dengan kedalaman HD. Kemudian ada \(H_{depth}\) (\(= P\times M\times HD\)) alamat ruang dalam keseluruhan jadual cincang. Selepas memasukkan \(H_{depth}\) entri ke dalam jadual cincang, akan ada \(N_{collison}\) (\(= R_{collison} \times H_{depth}\)) entri tidak boleh dimasukkan ke dalam jadual hash akhirnya.

Oleh itu, kapasiti CAM \(C_{depth}\) diperlukan hendaklah sama dengan bilangan entri bercanggah.

\[\begin{equation*} C_{depth}=N_{collision}=R_{collision}\times(P\times M\times HD). \tag{2} \end{equation*}\]

CAM pada setiap saluran sepatutnya CD, dan

\[\begin{equation*} CD=\frac{C_{depth}}{P}. \tag{3} \end{equation*}\]

4.3 Ketekalan

Disebabkan kependaman dalam pengiraan cincang dan operasi baca/tulis SRAM, terdapat dua senario ekstrem di mana isu ketekalan mungkin berlaku: (i) kunci yang ditanya adalah sama dengan kunci memasukkan; (ii) dalam set jadual cincang, kunci sedang dimasukkan, kunci yang dimasukkan baharu mengambil alamat sisipan kunci sisipan sebagai alamat calonnya.

Bagi yang pertama, jika kunci carian yang sama mengakses jadual padanan semasa proses menulis entri, ia mungkin mengakibatkan hasil pertanyaan yang salah. Untuk yang terakhir, status alamat yang dimasukkan dikemas kini kepada keadaan yang diduduki hanya selepas entri dimasukkan sepenuhnya. Dalam tempoh sisipan ini, ruang alamat masih dianggap dipilih untuk entri sisipan berikutnya, yang boleh menyebabkan perlanggaran antara dua entri apabila memilih alamat.

Walau bagaimanapun, kebarangkalian dan kesan kedua-dua senario ini boleh diabaikan. Pertama, berbanding dengan operasi pertanyaan, operasi sisipan biasanya jarang berlaku. Selain itu, sangat jarang berlaku perlanggaran berbilang alamat tunggal dalam jadual yang begitu luas, terutamanya dalam tempoh masa yang sangat singkat. Kes pertama telah dibincangkan untuk diabaikan dalam kerja terdahulu [10]. Dalam kes kedua, entri boleh dimasukkan daripada saluran paip yang berbeza dengan cara round-robin, atau entri baharu boleh dimasukkan selepas mengesahkan bahawa entri sebelumnya telah menyelesaikan operasi sisipan.

5. Pelaksanaan dan Penilaian

5.1 Perlaksanaan

Kami melaksanakan reka bentuk kami pada peranti FPGA Alveo U250 [22], yang mempunyai 1,728,000 LUT, 3,456,000 Flip-flop, 2688 blok memori BRAM36K dan 1280 blok memori URAM. Untuk membuat pertukaran antara kependaman dan daya pemprosesan, jadual EM mempunyai sejumlah 4 saluran dalam pelaksanaan kami, setiap saluran mempunyai set jadual cincang dan EM berasaskan CAM tambahan. Setiap set jadual cincang mempunyai 64 blok jadual cincang dengan kedalaman 4K. Berdasarkan kadar perlanggaran cincang, boleh ditentukan bahawa entri CAM 4K adalah mencukupi untuk menyimpan entri perlanggaran jadual cincang. Oleh itu, kedalaman CAM setiap saluran paip ialah 1K. Jumlah EM boleh menyimpan 1048K (4*64*4096=1048576) entri.

5.2 Penggunaan Memori

Sumber storan SRAM pada FPGA adalah unit bebas, dan setiap unit SRAM mesti digunakan mengikut blok. Kami menggunakan URAM untuk melaksanakan jadual cincang dan transpos BRAM untuk melaksanakan CAM. Di sini, setiap blok URAM dikonfigurasikan sebagai SRAM 4K*72b dan setiap blok BRAM36K dikonfigurasikan sebagai SRAM 512*72b. Simbol bagi \(\left \lceil *\right\rceil\) mewakili pembulatan.

Bilangan URAM yang digunakan oleh setiap blok jadual hash ialah

\[\begin{equation*} HTBUN=\left \lceil \frac{HD}{4096} \right \rceil\times{\left\lceil \frac{K+V+1}{72}\right\rceil}. \tag{4} \end{equation*}\]

Bilangan URAM yang digunakan oleh setiap set jadual hash ialah

\[\begin{equation*} HTSUN=M\times \left(\left \lceil \frac{HD}{4096} \right \rceil\times{\left\lceil \frac{K+V+1}{72}\right \rceil}\right). \tag{5} \end{equation*}\]

Bilangan BRAM36K yang digunakan oleh setiap jadual EM berasaskan CAM ialah

\[\begin{equation*} CAMBN=\left \lceil \frac{K}{log_2^{512}}\right \rceil \times \left \lceil \frac{CD}{72}\right \rceil+\left \lceil \frac{CD}{512}\right \rceil \times \left \lceil\frac{V}{72} \right \rceil. \tag{6} \end{equation*}\]

Jumlah blok memori yang digunakan oleh keseluruhan jadual EM ialah TUN blok URAM dan TBN BRAM36K blok, di mana

\[\begin{equation*} TUN=P\times \left(M\times\left(\left \lceil \frac{HD}{4096} \right \rceil\times{\left\lceil \frac{K+V+1}{72}\right \rceil}\right)\right), \tag{7} \end{equation*}\]

and

\[\begin{equation*} TBN=P\times\left(\left \lceil \frac{K}{log_2^{512}}\right \rceil \times \left \lceil \frac{CD}{72}\right \rceil+\left \lceil \frac{CD}{512}\right \rceil \times \left \lceil\frac{V}{72} \right \rceil\right). \tag{8} \end{equation*}\]

Jadual 2 menunjukkan penggunaan sumber untuk lebar kunci dan nilai yang berbeza dalam pelaksanaan kami. Dalam keseluruhan Jadual EM, terdapat 1048K ruang alamat dalam jadual cincang dan ruang alamat 4K untuk menyimpan entri bercanggah dalam jadual EM berasaskan CAM. Secara amnya, pekerjaan sumber logik kekal dalam julat yang munasabah, yang menyimpan sumber dan ruang frekuensi yang mencukupi untuk pelaksanaan aplikasi on-board yang lain. Penggunaan sumber storan adalah berkadar terus dengan lebar kunci atau nilai. Walau bagaimanapun, dalam beberapa kes, kerana SRAM mesti digunakan dalam unit keseluruhan blok, mungkin terdapat sisa simpanan, yang tidak dapat dielakkan dalam pelaksanaan FPGA. Di samping itu, apabila kedalaman jadual padanan kekal malar, peningkatan lebar boleh menyebabkan pengurangan frekuensi boleh dicapai. Ini kerana meningkatkan lebar memerlukan lebih banyak sumber on-board dan boleh mengakibatkan penghalaan yang lebih kompleks dan laluan perambatan isyarat yang lebih panjang. Ini meningkatkan kelewatan wayar dan mengehadkan kekerapan pengendalian keseluruhan jadual padanan.

Jadual 2  Penggunaan sumber 1048K entri jadual padanan tepat pada U250 FPGA.

5.3 Penilaian Prestasi

Untuk setiap set jadual cincang, kadar perlanggarannya ialah \(r_{collison}\), yang juga bermaksud kebarangkalian pemindahan daripada satu set jadual cincang ke saluran bersebelahan selepas kegagalan sisipan. Seperti yang dapat dilihat daripada Rajah 10(d), apabila terdapat bilangan blok jadual cincang yang lebih besar, hampir semua entri boleh berjaya dimasukkan ke dalam set jadual cincang pertamanya. Mengambil contoh apabila setiap set jadual hash mempunyai 64 blok jadual hash (iaitu, M=64), kadar perlanggaran \(r_{collison}\) adalah lebih kurang 0.00785, yang bermaksud entri jarang berpindah ke saluran lain untuk dimasukkan. Oleh itu, kelajuan pemasukan akan dipertingkatkan dengan berkesan oleh berbilang saluran saluran paip selari.

Untuk pertanyaan, jumlah bilangan ruang alamat dalam setiap set jadual cincang adalah sama, jadi kedalaman setiap set jadual cincang adalah \(\frac{1}{P}\) daripada keseluruhan jadual (di sini jangan pertimbangkan bilangan entri minimum dalam CAM), dan kebarangkalian pertanyaan yang berjaya untuk setiap entri jadual dalam jadual semasa ialah \(\frac{1}{P}\). Secara purata, bilangan jangkaan set jadual cincang untuk disoal bagi setiap entri jadual boleh ditandakan sebagai Ep. Oleh itu, dalam kes purata, ia bersamaan dengan mempunyai \(\frac{P}{Ep}\) saluran berfungsi selari dalam jadual EM kami.

Jumlah jadual yang dijangka akan disoal bagi setiap entri ialah

\[\begin{align} E_p&=\frac{1}{P}+2\frac{1}{P}\left(1-\frac{1}{P}\right)+\cdots +i\frac{1}{P}\left(1-\frac{1}{P}\right)^{i-1}+\cdots\nonumber\\ &\quad +(P-1)\frac{1}{P}\left(1-\frac{1}{P}\right)^{P-2} +P\left(1-\frac{1}{P}\right)^{P-1}, \tag{9} \\ & =\sum^{P-1}_{i=1}\left(\frac{i}{P}\left(1-\frac{1}{P}\right)^{i-1}\right) +P\left(1-\frac{1}{P}\right)^{P-1}. \tag{10} \end{align}\]

Untuk keseluruhan jadual EM, walaupun setiap operasi mempunyai kependaman tertentu, kedua-dua operasi sisipan dan operasi pertanyaan disambungkan. Oleh itu, jadual EM boleh lakukan \(\frac{P}{Ep}\) operasi setiap kitaran jam secara purata. Oleh itu, daya tampung operasi jadual EM ialah

\[\begin{equation*} Operation\ Throughput=\frac{P}{Ep}*Freq. \tag{11} \end{equation*}\]

Untuk paket, daya tampung teori yang boleh dicapai ialah

\[\begin{equation*} Throughput=\frac{P}{Ep}*Freq*(Pkt\ Len+20)B. \tag{12} \end{equation*}\]

20 bait tambahan adalah overhed tambahan pemindahan paket dalam rangkaian, yang termasuk: 12 bait jurang antara bingkai (IFG) yang merupakan jurang bingkai minimum paket Ethernet (IEEE 802.3), 7 bait mukadimah untuk penyegerakan jam dan 1 bait permulaan bagi pembatas bingkai (SFD) untuk mengenal pasti permulaan bingkai.

Dalam pelaksanaan kami, bilangan saluran paip ialah 4. Bila P adalah 4, \(Ep (P=4) \approx2.73\), dan\(\frac{P}{Ep}\approx1.46\). Oleh itu, jadual EM boleh mengendalikan 1.46 operasi setiap kitaran jam secara purata. Mengikut kekerapan pelaksanaan EM dalam Jadual 2, kita boleh mengira daya tampung operasi dan daya tampung paket yang disokong bagi jadual EM dalam kes yang berbeza.

Rajah 11 menunjukkan bilangan operasi pertanyaan yang boleh dikendalikan oleh EM sesaat dan daya pemprosesan paket 64B yang sepadan dalam keadaan berbeza. Jadual EM yang lebih kecil adalah mudah untuk mencapai daya pemprosesan yang lebih tinggi kerana ia boleh mencapai frekuensi kerja yang lebih tinggi. Secara keseluruhannya, keseluruhan jadual EM boleh memproses lebih daripada 200 juta operasi sesaat, dan boleh mencapai daya pemprosesan kira-kira 125 Gbps untuk paket 64B.

Rajah 11  Throughput di bawah konfigurasi EM yang berbeza. (a) Kapasiti operasi. (b) Kemasukan paket dengan panjang 64B.

6. Kerja dan Perbincangan Berkaitan

Jadual padanan tepat ialah tempat liputan penyelidikan dan digunakan secara meluas dalam pangkalan data, stor nilai kunci dan klasifikasi paket dsb., dan jadual padanan tepat berasaskan cincang ialah kaedah arus perdana pada pelaksanaan FPGA. Penyelidik memberi tumpuan terutamanya pada pengembangan skala, pengendalian perlanggaran cincang dan peningkatan daya pemprosesan jadual cincang pada FPGA, yang juga merupakan kerja utama kami dalam kertas kerja ini.

Dengan pengembangan berterusan skala rangkaian, saiz jadual padanan juga meningkat. Walaupun jadual cincang adalah struktur yang cekap storan, pelaksanaan jadual padanan yang besar pada FPGA masih akan menghadapi masalah seperti melaksanakan kesukaran, kekangan sumber, dan pengurangan kekerapan dll. Selain itu, menyelesaikan masalah perlanggaran cincang adalah salah satu cabaran utama untuk dicapai jadual padanan yang tepat. Penyelidik menggunakan kaedah yang berbeza untuk mengurangkan perlanggaran, seperti menggunakan fungsi cincang yang lebih baik, kaedah pengalamatan terbuka, kaedah rantai, dll. Melaksanakan algoritma resolusi perlanggaran pada FPGA perlu mempertimbangkan keseimbangan antara kecekapan penggunaan sumber perkakasan dan daya pemprosesan. Untuk meningkatkan daya pengeluaran, para penyelidik meneroka pelbagai pendekatan. Sebagai contoh, akses selari dicapai dengan menanya dan memanipulasi berbilang baldi cincang secara selari.

YZ Li [16] mencadangkan skim cincang tanpa perlanggaran menggunakan penapis mekar (BF) dan CAM untuk memastikan setiap carian mengakses memori paling banyak sekali. CAM tambahan digunakan untuk menyimpan entri bercanggah jadual cincang. Dan penapis bloom untuk pra-mengesan jika entri berada dalam jadual cincang memastikan setiap carian mengakses jadual cincang atau CAM paling banyak sekali. Ia mencapai prestasi kes terburuk yang lebih baik dan mempunyai fleksibiliti yang lebih besar untuk memasukkan atau membuat pertanyaan entri dengan cepat. Walau bagaimanapun, penapis bloom mempunyai beberapa masalah seperti kesukaran memadam, dan ia menggunakan banyak sumber apabila melaksanakan jadual padanan yang besar, yang tidak boleh dilaksanakan dalam amalan.

M. Sha [5] mencadangkan untuk menyelesaikan konflik hash cuckoo dengan menggunakan satu set RAM teragih sebagai storan tambahan, yang sebenarnya merupakan CAM kecil yang dilaksanakan oleh RAM dan daftar yang diedarkan. Walau bagaimanapun, ia mempunyai skalabiliti terhad terutamanya di bawah keperluan kedalaman CAM yang lebih besar apabila jadual padanan mempunyai kedalaman yang besar. Tambahan, mungkin terdapat ketidakpastian dalam masa sisipan dalam reka bentuk ini kerana pencincangan cuckoo dan entri dalam jadual lanjutan boleh ditulis semula ke dalam jadual cincang.

Yang et al. [10] mencadangkan FASTHash untuk mengoptimumkan pemprosesan jadual cincang melalui berbilang reka bentuk saluran paip selari. Dalam reka bentuk ini, ia menjalankan replikasi memori pada setiap saluran paip, yang bermaksud jadual dalam setiap saluran paip adalah sama. Walaupun ia meningkatkan daya pemprosesan jadual cincang, ia menggunakan sumber storan yang hebat untuk menyimpan peraturan yang sama berbilang kali, dan tidak mungkin untuk melakukan replikasi memori pada FPGA terhad sumber apabila saiz jadual padanan sangat besar. Selain itu, walaupun reka bentuk menyimpan berbilang slot untuk setiap ruang alamat untuk mengelakkan perlanggaran cincang, ia tidak menyelesaikan konflik cincang dengan lebih teliti. Dalam sesetengah kes, masih terdapat entri yang tidak boleh dimasukkan dengan jayanya.

Salvatore Pontarelli Pedro Reviliego et al. [11] membandingkan pelaksanaan jadual cincang saluran paip bersiri, selari dan selari, dan cadangan pelaksanaan saluran paip d selari yang meningkatkan daya pemprosesan dengan mengakses jadual secara selari. Walau bagaimanapun, perlanggaran cincang dalam pencincangan cuckoo tidak lagi dapat diselesaikan dalam reka bentuk ini.

WQ Wu et al. [12] memperkenalkan CAM ke dalam d-Pipeline untuk menangani perlanggaran cincang dengan lebih lanjut dan mengekalkan daya pemprosesan tinggi jadual cincang selari. Walau bagaimanapun, struktur hanya mempunyai satu unit CAM selepas berbilang jadual cincang. Apabila faktor beban jadual cincang adalah tinggi, pemasukan jadual cincang adalah sukar dan berbilang entri bercanggah perlu mengakses CAM secara serentak. Selain itu, CAM yang digunakannya memerlukan 16 kitaran jam untuk menyelesaikan operasi tulis. Dihadkan oleh kelajuan menulis CAM, jika ada entri untuk ditulis kepada CAM, jadual cincang perlu terhenti dan menunggu siap. CAM tidak boleh disesuaikan dengan jadual cincang selari dengan daya pemprosesan yang tinggi. Di samping itu, masalah tersusun tidak dipertimbangkan dalam reka bentuk, dan ia tidak boleh digunakan dalam beberapa senario yang memerlukan urutan paket rangkaian.

Jadual 3 menunjukkan perbandingan kerja kami dengan kaedah sedia ada. Berdasarkan pertimbangan sumber, kami tidak menggunakan penapis bloom dalam reka bentuk kami seperti BF-HASH-CAM [16]. Berbanding [5], ia tidak menggantikan entri sedia ada dalam sisipan apabila perlanggaran berlaku dalam reka bentuk kami, yang mengelakkan kependaman sisipan yang tidak menentu yang disebabkan oleh pencincangan cuckoo. Dengan berkongsi jadual padanan peraturan antara berbilang saluran saluran paip, kaedah kami mengelakkan replikasi storan dalam FASTHash [10] dan meningkatkan daya pemprosesan. Pada masa yang sama, faktor beban dipertingkatkan dengan menambah bilangan blok jadual cincang, dan konflik cincang dikendalikan oleh unit CAM tambahan. Di samping itu, untuk senario pemprosesan paket rangkaian, kertas kerja ini secara khusus mempertimbangkan pemulihan tertib dalam berbilang saluran saluran paip selari, yang tidak dipertimbangkan dalam reka bentuk d-Pipeline [11] dan [12].

Jadual 3  Perbandingan dengan kaedah lain.

Sebenarnya, terdapat beberapa produk atau penyelesaian SmartNIC khusus untuk memuatkan pemprosesan paket SDN tahun-tahun ini, seperti siri Nvidia's ConnectX [23], Xilinx's Alveo U25 [24] dan SN1000 [25] SmartNICs, Microsoft's Bluebird [26] dsb. jadual ialah modul bebas platform, ia boleh dibenamkan ke dalam sistem ini untuk menyokong pemprosesan paket SDN juga.

7. Kesimpulan

Secara ringkasnya, kertas kerja ini membentangkan jadual EM bebas perlanggaran throughput tinggi berskala besar yang berkongsi jadual peraturan dan pemulihan tersusun di antara berbilang saluran paip selari untuk aplikasi paket rangkaian berdasarkan FPGA. Dengan berbilang saluran yang berfungsi secara selari dan berkongsi jadual peraturan mereka, daya pemprosesan keseluruhan jadual meningkat kira-kira 1.5 kali tanpa replikasi storan. Semua keputusan yang sepadan akan disusun semula untuk memastikan urutan operasi dan kependaman pemprosesan yang berterusan dalam setiap saluran paip. Selain itu, ia mengurangkan kadar perlanggaran melalui berbilang blok jadual cincang, dan menyimpan entri bercanggah ke dalam jadual CAM tambahan. Jadual padanan tepat yang dilaksanakan menyokong 200 juta operasi pertanyaan sesaat, yang cukup untuk menyokong pemprosesan melebihi 100 Gbps walaupun untuk paket 64B.

Penghargaan

Penyelidikan ini dibiayai oleh Program Penyelidikan dan Pembangunan Utama Negara China: Cip sambung yang ditakrifkan perisian dan pembangunan kit perisian sokongan (Project.No. 2022YFB2901004).

Rujukan

[1] P. Bosshart, D. Daly, G. Gibb, M. Izzard, N. McKeown, J. Rexford, C. Schlesinger, D. Talayco, A. Vahdat, G. Varghese, and D. Walker, “P4: Programming protocol-independent packet processors,” SIGCOMM Comput. Commun. Rev., vol.44, no.3, pp.87-95, July 2014.
CrossRef

[2] P. Bosshart, G. Gibb, H.-S. Kim, G. Varghese, N. McKeown, M. Izzard, F. Mujica, and M. Horowitz, “Forwarding metamorphosis: Fast programmable match-action processing in hardware for SDN,” ACM SIGCOMM Comput. Commun. Rev., vol.43, no.4, pp. 99-110, 2013.
CrossRef

[3] R. Shubbar and M. Ahmadi, “Fast 2D filter with low false positive for network packet inspection,” IET Networks, vol.6, no.6, pp.224-231, 2017.
CrossRef

[4] P. Reviriego, G. Levy, M. Kadosh, and S. Pontarelli, “Algorithmic tcams: Implementing packet classification algorithms in hardware,” IEEE Commun. Mag., vol.60, no.9, pp.60-66, 2022.
CrossRef

[5] M. Sha, Z. Guo, K. Wang, and X. Zeng, “A high-performance and accurate FPGA-based flow monitor for 100 Gbps networks,” Electronics, vol.11, no.13, p.1976, 2022.
CrossRef

[6] M. Sha, Z. Guo, and M. Song, “A review of FPGA’s application in high-speed network processing,” J. Network New Media, vol.10, pp.1-11, 2021.

[7] M. Irfan, A.I. Sanka, Z. Ullah, and R.C. Cheung, “Reconfigurable content-addressable memory (CAM) ON FPGAs: A tutorial and survey,” Future Generation Computer Systems, vol.128, pp.451-465, 2022.
CrossRef

[8] J. Carter and M. Wegman, “Universal classes of hash functions (extended abstract),” Proc. ninth Annual ACM Symposium on Theory of Computing, STOC’77, pp.106-112, 1977.
CrossRef

[9] R. Pagh and F.F. Rodler, “Cuckoo hashing,” J. Algorithms, vol.51, no.2, pp.122-144, 2004.
CrossRef

[10] Y. Yang, S.R. Kuppannagari, A. Srivastava, R. Kannan, and V.K. Prasanna, “FASTHash: FPGA-based high throughput parallel hash table,” Proc. 35th International Conference, ISC High Performance 2020, High Performance Computing, Frankfurt/Main, Germany, pp.3-22, Springer, June 2020.
CrossRef

[11] S. Pontarelli, P. Reviriego, and J.A. Maestro, “Parallel d-pipeline: A cuckoo hashing implementation for increased throughput,” IEEE Trans. Comput., vol.65, no.1, pp.326-331, 2015.
CrossRef

[12] W.-Q. Wu, M.-T. Xue, T.-Q. Zhu, Z.-G. Ma, and F. Yu, “High-throughput parallel SRAM-based hash join architecture on FPGA,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol.67, no.11, pp.2502-2506, 2020.
CrossRef

[13] M. Kekely and J. Korenek, “Mapping of P4 match action tables to FPGA,” 2017 27th International Conference on Field Programmable Logic and Applications (FPL), IEEE, pp.1-2, 2017.
CrossRef

[14] D.-H. Le, K. Inoue, and C.-K. Pham, “Design a fast CAM-based exact pattern matching system on FPGA and 0.18 μm CMOS process,” IEICE Trans. Fundamentals, vol.E96-A, no.9, pp.1883-1888, Sept. 2013.
CrossRef

[15] Z. István, G. Alonso, M. Blott, and K. Vissers, “A flexible hash table design for 10 GBPS key-value stores on FPGAS,” 2013 23rd International Conference on Field Programmable Logic and Applications, IEEE, pp.1-8, 2013.
CrossRef

[16] Y. Li, “Non-collision hash scheme using Bloom filter and CAM,” 2009 Second Pacific-Asia Conference on Web Mining and Web-based Application, IEEE, pp.55-58, 2009.
CrossRef

[17] M. Kekely, L. Kekely, and J. Korenek, “Memory aware packet matching architecture for high-speed networks,” 2018 21st Euromicro Conference on Digital System Design (DSD), IEEE, pp.1-8, 2018.
CrossRef

[18] M. Ramakrishna, E. Fu, and E. Bahcekapili, “Efficient hardware hashing functions for high performance computers,” IEEE Trans. Comput., vol.46, no.12, pp.1378-1381, 1997.
CrossRef

[19] H. Krawczyk, “LFSR-based hashing and authentication,” Proc. 14th Annual International Cryptology Conference, Advances in Cryptology ― CRYPTO’94, Santa Barbara, California, USA, pp.129-139, Springer, Aug. 1994.
CrossRef

[20] W. Jiang, “Scalable ternary content addressable memory implementation using FPGAs,” Architectures for Networking and Communications Systems, IEEE, pp.71-82, 2013.
CrossRef

[21] G.H. Gonnet, “Expected length of the longest probe sequence in hash code searching,” J. ACM (JACM), vol.28, no.2, pp.289-304, 1981.
CrossRef

[22] Xilinx, “Alveo u200 and u250 data center accelerator cards data sheet (ds962),” Online, 2023, https://docs.xilinx.com/r/en-US/ds962-u200-u250
URL

[23] Nvidia, “ConnectX-7 400G Adapters,” Online, 2023, https://nvdam.widen.net/s/csf8rmnqwl.infiniband-ethernet-datasheet-connectx-7-ds-nv-us-2544471
URL

[24] Xilinx, “Alveo U25 Product Brief,” Online, 2023, https://www.xilinx.com/content/dam/xilinx/publications/product-briefs/alveo-u25-product-brief.pdf
URL

[25] Xilinx, “Alveo SN1000 SmartNICs Data Sheet (DS989),” Online, 2023, https://docs.xilinx.com/v/u/en-US/ds989-sn1000
URL

[26] M. Arumugam, D. Bansal, N. Bhatia, J. Boerner, S. Capper, C. Kim, S. McClure, N. Motwani, R. Narasimhan, U. Panchal, T. Pimpo, A. Premji, P. Shrivastava, and R. Tewari, “Bluebird: High-performance SDN for bare-metal cloud services,” 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), Renton, WA, pp.355-370, USENIX Association, April 2022.

Pengarang

Xiaoyong SONG
  Chinese Academy of Sciences,University of Chinese Academy of Sciences

received the B.S. degree from Beijing University of Technology, Beijing, China, in 2019. He is currently pursuing the doctor’s degree with the School of Electronic, Electrical and Communication Engineering, University of Chinese Academy of Sciences, Beijing. His current research interest includes FPGA network acceleration, and matching table etc.

Zhichuan GUO
  Chinese Academy of Sciences,University of Chinese Academy of Sciences

received the B.S. degree from Wuhan University in 1996, and the Ph.D. degree from the University of Science and Technology of China in 2006. From 1996 to 2003, he served as an Electronics Engineer with the 13th Research Institute of China Electronics Technology Group Corporation and a SDH hardware R&D system engineer of optical networks at Huawei. In 2006, he joined with the Institute of Acoustics, Chinese Academy of Sciences, Beijing, China. Now he is a Professor of CAS engaging in field programmable gate array (FPGA)-based code acceleration, VLSI, and security.

Xinshuo WANG
  Chinese Academy of Sciences,University of Chinese Academy of Sciences

received the B.E. degree from Chongqing University of Posts and Telecommunications, Chongqing, China, in 2021. At present, he is studying for a doctorate degree in the school of electronic. electrical and communication engineering of the University of Chinese Academy of Sciences in Beijing, focusing on the field of FPGA network acceleration.

Mangu SONG
  Chinese Academy of Sciences,Suzhou Haiwang Network Technologies Co., Ltd.

is currently working at the Institute of Acoustics, Chinese Academy of Sciences (IACAS), as a research assistant. She received her M.Sc degree in electronics and communication engineering from the School of Microelectronics, Chinese Academy of Science, Beijing, China in 2017. Her current research interests include FPGA-based code acceleration and network security.

Kata kunci