在 GPU 上實現高效能精確字串搜尋 (Exact String Matching),關鍵在於記憶體存取模式優化、平行化策略與同步機制。本文詳細解析基於 OpenCL 的大文本模式搜尋核心函數實作,涵蓋 Local Memory 快取模式串、Global Memory 合併存取、Work-group 分工與原子計數器同步。
| 層級 | 機制 | 用途 |
| Work-group 內 | barrier(CLK_LOCAL_MEM_FENCE) | 確保模式串完整載入 Local Memory 後再開始搜尋 |
| Work-group 內 | barrier(CLK_GLOBAL_MEM_FENCE) | 確保 Global Memory 寫入可見性 (較少用) |
| 跨 Work-group | Global Memory 原子操作 atomic_inc | 結果計數器與結果緩衝區索引分配,保證無競爭 |
核心函數完整實作 (string_search_kernel.cl)
int compare(__global const uchar* text, __local const uchar* pattern, uint length) {
for (uint l = 0; l < length; l++) {
if (text[l] != pattern[l])
return 0;
}
return 1;
}
__kernel void StringSearch(
__global uchar* text, // 輸入文本
const uint textLength, // 文本長度
__global const uchar* pattern, // 模式串
const uint patternLength, // 模式長度
const uint maxSearchLength, // 每 work-group 最大搜尋位置數
__global int* resultCount, // 結果計數器 (全域)
__global int* resultBuffer, // 匹配位置緩衝區 (全域)
__local uchar* localPattern // Local Memory 模式串緩衝
) {
int localIdx = get_local_id(0);
int localSize = get_local_size(0);
int groupIdx = get_group_id(0);
// 計算本 work-group 負責的搜尋範圍
uint lastSearchIdx = textLength - patternLength + 1;
uint beginSearchIdx = groupIdx * maxSearchLength;
uint endSearchIdx = beginSearchIdx + maxSearchLength;
if (beginSearchIdx > lastSearchIdx) return;
if (endSearchIdx > lastSearchIdx) endSearchIdx = lastSearchIdx;
// 協作載入模式串到 Local Memory
for (int idx = localIdx; idx < patternLength; idx += localSize) {
localPattern[idx] = pattern[idx];
}
barrier(CLK_LOCAL_MEM_FENCE); // 關鍵:確保所有執行緒看到完整模式串
// 平行搜尋:每個執行緒處理範圍內的部分位置
for (uint stringPos = beginSearchIdx + localIdx;
stringPos < endSearchIdx;
stringPos += localSize) {
if (compare(text + stringPos, localPattern, patternLength) == 1) {
// 原子操作獲取唯一索引寫入結果
int count = atomic_inc(resultCount);
resultBuffer[count] = stringPos;
// printf("%d ", stringPos); // 除錯用,需裝置支援 printf
}
}
barrier(CLK_LOCAL_MEM_FENCE); // 確保寫入完成 (可選)
}
主機端啟動配置
// 計算 work-group 數量與大小
size_t localSize = 256; // 每 work-group 執行緒數
size_t maxSearchPerGroup = 1024; // 每群組處理位置數
size_t globalSize = ((textLength - patternLength + 1) + maxSearchPerGroup - 1) / maxSearchPerGroup * localSize;
// 配置 Local Memory 大小 (模式串長度)
cl_mem localPatternMem = clCreateBuffer(context, CL_MEM_LOCAL, patternLength, NULL, &err);
// 設定核心參數
clSetKernelArg(kernel, 0, sizeof(cl_mem), &textBuffer);
clSetKernelArg(kernel, 1, sizeof(cl_uint), &textLength);
clSetKernelArg(kernel, 2, sizeof(cl_mem), &patternBuffer);
clSetKernelArg(kernel, 3, sizeof(cl_uint), &patternLength);
clSetKernelArg(kernel, 4, sizeof(cl_uint), &maxSearchPerGroup);
clSetKernelArg(kernel, 5, sizeof(cl_mem), &resultCountBuffer);
clSetKernelArg(kernel, 6, sizeof(cl_mem), &resultBuffer);
clSetKernelArg(kernel, 7, sizeof(cl_mem), NULL); // Local Memory 由 runtime 分配
// 執行
clEnqueueNDRangeKernel(queue, kernel, 1, NULL, &globalSize, &localSize, 0, NULL, NULL);
效能優化要點
- 向量化載入:模式串載入可用 `uchar4`/`uint4` 向量類型,減少指令數。
- 邊界條件優化:最後一個 work-group 範圍裁剪避免越界。
- 提前退出:`compare` 函數首字元不匹配即返回,減少分支發散。
- 結果緩衝區預分配:按最大可能匹配數分配,或雙階段 (先計數再分配)。
- 重疊搜尋範圍:相鄰 work-group 邊界需重疊 `patternLength - 1` 位元組,避免跨邊界匹配遺漏 (上述代碼簡化未處理,實際需補充)。
裝置能力查詢
// 檢查原子操作支援
cl_device_info ext = clGetDeviceInfo(device, CL_DEVICE_EXTENSIONS, ...);
// 確認 "cl_khr_int64_base_atomics", "cl_khr_int64_extended_atomics"
// 或 OpenCL 2.0+ 核心原子操作
圖示裝置擴展支援原子操作與 printf:

擴展:近似搜尋與正則表達式
精確搜尋是基礎。進階需求可考慮:
- Bitap 演算法 (移位或運算) 在 GPU 上平行化。
- Aho-Corasick 多模式匹配,構建失敗函數圖在 GPU 上遍歷。
- 正則表達式 NFA/DFA 模擬 (如 RE2C 生成核心代碼)。
copyright ©
萬盛學電腦網 all rights reserved