Skip to content

Instantly share code, notes, and snippets.

@lowener

lowener/CAGRA_tutorial.ipynb

Last active June 24, 2024 11:23
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save lowener/7c305fd61d07c25e34077bf90f4ee8aa to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save lowener/7c305fd61d07c25e34077bf90f4ee8aa to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
CAGRA_tutorial.ipynb
{
"cells": [
{
"cell_type": "markdown",
"id": "827c465f",
"metadata": {},
"source": [
"# RAFT CAGRA tutorial"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "ed3b5d98",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Requirement already satisfied: adjustText in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (1.0.3)\n",
"Requirement already satisfied: h5py in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (3.10.0)\n",
"Requirement already satisfied: matplotlib in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (3.8.2)\n",
"Requirement already satisfied: numpy in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from adjustText) (1.26.3)\n",
"Requirement already satisfied: scipy in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from adjustText) (1.11.4)\n",
"Requirement already satisfied: contourpy>=1.0.1 in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from matplotlib) (1.2.0)\n",
"Requirement already satisfied: cycler>=0.10 in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from matplotlib) (0.12.1)\n",
"Requirement already satisfied: fonttools>=4.22.0 in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from matplotlib) (4.47.2)\n",
"Requirement already satisfied: kiwisolver>=1.3.1 in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from matplotlib) (1.4.5)\n",
"Requirement already satisfied: packaging>=20.0 in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from matplotlib) (23.2)\n",
"Requirement already satisfied: pillow>=8 in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from matplotlib) (10.0.0)\n",
"Requirement already satisfied: pyparsing>=2.3.1 in /home/mide/miniconda3/envs/all_cuda-120_arch-x86_64/lib/python3.10/site-packages (from matplotlib) (3.1.1)\n",
"Requirement already satisfied: python-dateutil>=2.7 in /home/mide/.local/lib/python3.10/site-packages (from matplotlib) (2.8.2)\n",
"Requirement already satisfied: six>=1.5 in /home/mide/.local/lib/python3.10/site-packages (from python-dateutil>=2.7->matplotlib) (1.16.0)\n"
]
}
],
"source": [
"!pip install adjustText h5py matplotlib"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "d00ef883",
"metadata": {},
"outputs": [],
"source": [
"import os\n",
"import tempfile\n",
"import cupy as cp\n",
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"import rmm\n",
"import urllib.request\n",
"import h5py\n",
"\n",
"from rmm.allocators.cupy import rmm_cupy_allocator\n",
"from pylibraft.common import DeviceResources\n",
"from pylibraft.neighbors import cagra\n",
"from adjustText import adjust_text\n",
"from utils import calc_recall, load_dataset\n",
"\n",
"%matplotlib inline"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "f52ace18",
"metadata": {},
"outputs": [],
"source": [
"# A clumsy helper for inspecting properties of an object\n",
"def show_properties(obj):\n",
" return {\n",
" attr: getattr(obj, attr)\n",
" for attr in dir(obj)\n",
" if type(getattr(type(obj), attr)).__name__ == 'getset_descriptor'\n",
" }"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "9883a61e",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The index and data will be saved in /tmp/raft_cagra_tutorial\n"
]
}
],
"source": [
"# We'll need to store some data in this tutorial\n",
"WORK_FOLDER = os.path.join(tempfile.gettempdir(), 'raft_cagra_tutorial')\n",
"\n",
"if not os.path.exists(WORK_FOLDER):\n",
" os.makedirs(WORK_FOLDER)\n",
"print(\"The index and data will be saved in\", WORK_FOLDER)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "a57cb311",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Tue Jan 16 15:37:18 2024 \n",
"+-----------------------------------------------------------------------------+\n",
"| NVIDIA-SMI 525.147.05 Driver Version: 525.147.05 CUDA Version: 12.0 |\n",
"|-------------------------------+----------------------+----------------------+\n",
"| GPU Name Persistence-M| Bus-Id Disp.A | Volatile Uncorr. ECC |\n",
"| Fan Temp Perf Pwr:Usage/Cap| Memory-Usage | GPU-Util Compute M. |\n",
"| | | MIG M. |\n",
"|===============================+======================+======================|\n",
"| 0 NVIDIA GeForce ... On | 00000000:1A:00.0 Off | N/A |\n",
"| 0% 56C P8 20W / 290W | 10MiB / 8192MiB | 0% Default |\n",
"| | | N/A |\n",
"+-------------------------------+----------------------+----------------------+\n",
"| 1 Quadro RTX 8000 On | 00000000:68:00.0 On | Off |\n",
"| 34% 45C P8 32W / 260W | 940MiB / 49152MiB | 2% Default |\n",
"| | | N/A |\n",
"+-------------------------------+----------------------+----------------------+\n",
" \n",
"+-----------------------------------------------------------------------------+\n",
"| Processes: |\n",
"| GPU GI CI PID Type Process name GPU Memory |\n",
"| ID ID Usage |\n",
"|=============================================================================|\n",
"| 0 N/A N/A 1412 G /usr/lib/xorg/Xorg 4MiB |\n",
"| 0 N/A N/A 2854 G /usr/lib/xorg/Xorg 4MiB |\n",
"| 1 N/A N/A 1412 G /usr/lib/xorg/Xorg 71MiB |\n",
"| 1 N/A N/A 2854 G /usr/lib/xorg/Xorg 270MiB |\n",
"| 1 N/A N/A 2991 G /usr/bin/gnome-shell 63MiB |\n",
"| 1 N/A N/A 3450 G ...AAAAAAAAA= --shared-files 51MiB |\n",
"| 1 N/A N/A 3881 G ...veSuggestionsOnlyOnDemand 97MiB |\n",
"| 1 N/A N/A 4331 G /usr/lib/firefox/firefox 192MiB |\n",
"| 1 N/A N/A 8185 G ...RendererForSitePerProcess 180MiB |\n",
"+-----------------------------------------------------------------------------+\n",
"WARNING: infoROM is corrupted at gpu 0000:68:00.0\n"
]
}
],
"source": [
"# Report the GPU in use to put the measurements into perspective\n",
"!nvidia-smi"
]
},
{
"cell_type": "markdown",
"id": "1f377e16",
"metadata": {},
"source": [
"## Use the pool memory resource\n",
"RAFT uses RMM allocator widely across its algorithms, including the performance-sensitive parts like CAGRA search.\n",
"It's strongly advised to set up the RMM pool memory resource to minimize the overheads of repeated CUDA allocations.\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "59b6f601",
"metadata": {},
"outputs": [],
"source": [
"pool = rmm.mr.PoolMemoryResource(\n",
" rmm.mr.CudaMemoryResource(),\n",
" initial_pool_size=2**30\n",
")\n",
"rmm.mr.set_current_device_resource(pool)\n",
"cp.cuda.set_allocator(rmm_cupy_allocator)"
]
},
{
"cell_type": "markdown",
"id": "554f5c1f",
"metadata": {},
"source": [
"## Get the data\n",
"The [ANN benchmarks website](https://ann-benchmarks.com) provides the datasets in [HDF5 format](https://www.hdfgroup.org/solutions/hdf5/).\n",
"\n",
"The list of prepared datasets can be found at https://github.com/erikbern/ann-benchmarks/#data-sets"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "e21506b0",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The index and data will be saved in /tmp/raft_example\n"
]
}
],
"source": [
"DATASET_URL = \"http://ann-benchmarks.com/gist-960-euclidean.hdf5\"\n",
"f = load_dataset(DATASET_URL)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "479ce9e7",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Loaded dataset of size (1000000, 128); metric: 'euclidean'.\n",
"Number of test queries: 10000\n"
]
}
],
"source": [
"metric = f.attrs['distance']\n",
"\n",
"dataset = cp.array(f['train'])\n",
"queries = cp.array(f['test'])\n",
"gt_neighbors = cp.array(f['neighbors'])\n",
"gt_distances = cp.array(f['distances'])\n",
"\n",
"print(f\"Loaded dataset of size {dataset.shape}; metric: '{metric}'.\")\n",
"print(f\"Number of test queries: {queries.shape[0]}\")"
]
},
{
"cell_type": "markdown",
"id": "d9fcf4ef",
"metadata": {},
"source": [
"## Build the index\n",
"Construction of the index consists of the building and optimization of the graph."
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "fd1ed1dd",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'graph_degree': 64, 'intermediate_graph_degree': 128, 'metric': 1}"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# RAFT's DeviceResources controls the GPU, cuda stream, memory policies etc.\n",
"# For now, we just create a default instance.\n",
"resources = DeviceResources()\n",
"\n",
"# We'll use the ANN-benchmarks-provided metric and sensible defaults for the rest of parameters.\n",
"index_params = cagra.IndexParams(intermediate_graph_degree=128, graph_degree=64, build_algo=\"nn_descent\", metric=metric)\n",
"\n",
"show_properties(index_params)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "58bdcd33",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 1min 48s, sys: 6.72 s, total: 1min 55s\n",
"Wall time: 29.6 s\n"
]
},
{
"data": {
"text/plain": [
"Index(type=CAGRA, metric=euclidean, metric=1, dim=960, graph_degree=64)"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"%%time\n",
"## Build the index\n",
"# This function takes a row-major either numpy or cupy (GPU) array.\n",
"# Generally, it's a bit faster with GPU inputs, but the CPU version may come in handy\n",
"# if the whole dataset cannot fit into GPU memory.\n",
"index = cagra.build(index_params, dataset, handle=resources)\n",
"# This function is asynchronous so we need to explicitly synchronize the GPU before we can measure the execution time\n",
"resources.sync()\n",
"index"
]
},
{
"cell_type": "markdown",
"id": "0d9f615d",
"metadata": {},
"source": [
"The total time here for the `cagra.build()` function is just under 30 seconds, for a dataset of 1 Million rows with a dimension of 960."
]
},
{
"cell_type": "markdown",
"id": "8dd30d46",
"metadata": {},
"source": [
"## Search\n",
"To perform a search we create a Search Params object containing the parameters that we need. The main adjustment knob will be the `itopk_size` parameter. Let's set it up to reach 95% accuracy."
]
},
{
"cell_type": "code",
"execution_count": 135,
"id": "64df9ede",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{'algo': 3,\n",
" 'hashmap_max_fill_rate': 0.5,\n",
" 'hashmap_min_bitlen': 0,\n",
" 'hashmap_mode': 2,\n",
" 'itopk_size': 100,\n",
" 'max_iterations': 0,\n",
" 'max_queries': 0,\n",
" 'min_iterations': 0,\n",
" 'num_random_samplings': 1,\n",
" 'rand_xor_mask': 1213332,\n",
" 'search_width': 1,\n",
" 'team_size': 0,\n",
" 'thread_block_size': 0}"
]
},
"execution_count": 135,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"k = 10\n",
"search_params = cagra.SearchParams(itopk_size=100)\n",
"show_properties(search_params)"
]
},
{
"cell_type": "code",
"execution_count": 138,
"id": "036280bb",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 39.4 ms, sys: 12 ms, total: 51.4 ms\n",
"Wall time: 50.2 ms\n"
]
}
],
"source": [
"%%time\n",
"distances, neighbors = cagra.search(search_params, index, queries, k, handle=resources)\n",
"# Sync the GPU to make sure we've got the timing right\n",
"resources.sync()"
]
},
{
"cell_type": "code",
"execution_count": 139,
"id": "23d8eaaf",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Got recall = 0.9525 with the default parameters (k = 10).\n"
]
}
],
"source": [
"recall_first_try = calc_recall(neighbors, gt_neighbors)\n",
"print(f\"Got recall = {recall_first_try} with the default parameters (k = {k}).\")"
]
},
{
"cell_type": "markdown",
"id": "dbc940be",
"metadata": {},
"source": [
"## Comparison with HNSW workflow at 95% recall\n",
"\n",
"Let's compare the CAGRA workflow with one of the standard library for vector search: HNSW.\n",
"\n",
"We build and search an HNSW index, and we can observe that the workflow is pretty similar.\n",
"This HNSW index has been set up to reach a recall of 95%, with a search time of under 500 ms.\n",
"The index build time for this configuration is much higher than CAGRA's, at a similar recall and search speed."
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "6780906c",
"metadata": {},
"outputs": [],
"source": [
"import hnswlib\n",
"import numpy as np"
]
},
{
"cell_type": "code",
"execution_count": 18,
"id": "c17c7dbb",
"metadata": {},
"outputs": [],
"source": [
"# Use same data\n",
"dataset_np = np.array(f['train'])\n",
"queries_np = np.array(f['test'])\n",
"gt_neighbors_np = np.array(f['neighbors'])\n",
"gt_distances_np = np.array(f['distances'])"
]
},
{
"cell_type": "code",
"execution_count": 25,
"id": "ead7d55f",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Adding 1000000 elements\n",
"CPU times: user 2h 19min 57s, sys: 24.5 s, total: 2h 20min 22s\n",
"Wall time: 6min 13s\n"
]
}
],
"source": [
"%%time\n",
"\n",
"# Initializing index\n",
"# max_elements - the maximum number of elements (capacity). Will throw an exception if exceeded\n",
"# during insertion of an element.\n",
"# The capacity can be increased by saving/loading the index, see below.\n",
"#\n",
"# ef_construction - controls index search speed/build speed tradeoff\n",
"#\n",
"# M - is tightly connected with internal dimensionality of the data. Strongly affects memory consumption (~M)\n",
"# Higher M leads to higher accuracy/run_time at fixed ef/efConstruction\n",
"p = hnswlib.Index(space='l2', dim=dataset_np.shape[1])\n",
"p.init_index(max_elements=dataset_np.shape[0], ef_construction=250, M=18)\n",
"\n",
"print(\"Adding %d elements\" % (len(dataset_np)))\n",
"p.add_items(dataset_np)"
]
},
{
"cell_type": "code",
"execution_count": 42,
"id": "15d3f0ee",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"CPU times: user 11.2 s, sys: 15.8 ms, total: 11.2 s\n",
"Wall time: 492 ms\n"
]
}
],
"source": [
"%%time\n",
"# Controlling the recall by setting ef:\n",
"# higher ef leads to better accuracy, but slower search\n",
"p.set_ef(305)\n",
"labels, distances = p.knn_query(queries_np, k=10)"
]
},
{
"cell_type": "code",
"execution_count": 43,
"id": "0f6ff138",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Got recall = 0.9509.\n"
]
}
],
"source": [
"recall_first_try = calc_recall(labels, gt_neighbors_np)\n",
"print(f\"Got recall = {recall_first_try}.\")"
]
},
{
"cell_type": "markdown",
"id": "e272fc50-d1a0-4d38-82e1-514f9515c413",
"metadata": {},
"source": [
" We can notice that the build and search time of CAGRA is largely outperforming HNSW, for the same recall level."
]
},
{
"cell_type": "markdown",
"id": "f84a45b7",
"metadata": {},
"source": [
"# CAGRA Mastery"
]
},
{
"cell_type": "markdown",
"id": "8ccc0f2a",
"metadata": {},
"source": [
"## Build parameters adjustments\n",
"\n",
"### Graph degree\n",
"\n",
"The `graph_degree` parameter represents the number of neighbors in the graph for each vector. This is the main parameter of CAGRA and heavily influence the build time, the search time, the search quality and the memory consumption.\n"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "93623b75",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"39.5 s ± 1.01 s per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
"40.2 s ± 339 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
"40.5 s ± 272 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
"40.7 s ± 214 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
"40.9 s ± 221 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
"40.9 s ± 454 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
"41.8 s ± 444 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n",
"42.7 s ± 436 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
},
{
"data": {
"text/plain": [
"Text(0, 0.5, 'build times (s)')"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
},
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAzgAAAGwCAYAAABl8MAeAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8g+/7EAAAACXBIWXMAAA9hAAAPYQGoP6dpAABG/ElEQVR4nO3de1xVdb7/8ffmIm4QvICbSyLhJa1MjVLGa5aITlNKp6kmm0mbZuwCllKKWlqZDeqUY3VKTzMntYtpp5FyzFBQobwbZOpUpGRWKmIXIUFxA+v3Rz/3tAMREFibxev5ePB47PVd3732Z32/D3C//a69ts0wDEMAAAAAYAFeZhcAAAAAAA2FgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACzDx+wCPFFlZaWOHDmiwMBA2Ww2s8sBAAAAWjTDMPTjjz8qIiJCXl41r9EQcKpx5MgRRUZGml0GAAAAgJ/5+uuv1alTpxr7EHCqERgYKOmnAQwKCjKtDqfTqfXr1ys+Pl6+vr6m1WFljLFnY37Mw9h7BubBPIy952AuzOUp419cXKzIyEjX+/SaEHCqcfaytKCgINMDjr+/v4KCgviFbiSMsWdjfszD2HsG5sE8jL3nYC7M5WnjX5uPj3CTAQAAAACWQcABAAAAYBkEHAAAAACWQcABAAAAYBkEHAAAAACWQcABAAAAYBkEHAAAAACWQcABAAAAYBkEHAAAAACWYWrASU1NVb9+/RQYGCiHw6GEhATl5eVV6bdt2zZdd911CggIUFBQkIYOHapTp07VeOwXXnhBF198sVq3bq3Y2Fjt3LmzsU4DAAAAgIcwNeBkZ2crMTFR27dvV0ZGhpxOp+Lj41VSUuLqs23bNo0aNUrx8fHauXOndu3apaSkJHl5nbv0lStXKjk5WY899phyc3PVp08fjRw5UoWFhU1xWgAAAABM4mPmi6enp7ttL126VA6HQzk5ORo6dKgkafLkyXrggQc0bdo0V78ePXrUeNwFCxboz3/+s+666y5J0uLFi/Xuu+/q5ZdfdjsOAAAAAGsxNeD8UlFRkSSpQ4cOkqTCwkLt2LFDd9xxhwYOHKj8/Hz17NlTTz31lAYPHlztMc6cOaOcnBxNnz7d1ebl5aW4uDht27at2ueUlZWprKzMtV1cXCxJcjqdcjqdDXJu9XH2tc2sweoYY8/G/JiHsfcMzIN5GHvPwVyYy1PGvy6vbzMMw2jEWmqtsrJSo0eP1okTJ7R582ZJ0vbt2zVgwAB16NBBTz/9tPr27atXXnlFL774ovbt26fu3btXOc6RI0d00UUXaevWrRowYICrferUqcrOztaOHTuqPOfxxx/XE088UaV9+fLl8vf3b8CzBAAAAFBXpaWlGjt2rIqKihQUFFRjX49ZwUlMTNS+fftc4Ub6KfRI0j333OO63OzKK6/Uhg0b9PLLLys1NbVBXnv69OlKTk52bRcXFysyMlLx8fHnHcDGcqr8lAa9OUiSlHVTloLs5tRhdU6nUxkZGRoxYoR8fX3NLge/wPyYh7H3DMyDeRh7z8FcmMtTxv/sFVa14REBJykpSWvWrNH777+vTp06udrDw8MlSZdddplb/0svvVRfffVVtccKCQmRt7e3jh075tZ+7NgxhYWFVfscPz8/+fn5VWn39fU1bSKd+s8ynJl1tBSMsWdjfszD2HsG5sE8jL3nYC7MZfb41+W1Tb2LmmEYSkpKUlpamjZu3Kjo6Gi3/RdffLEiIiKq3Dr6888/V1RUVLXHbNWqla666ipt2LDB1VZZWakNGza4XbIGAAAAwHpMXcFJTEzU8uXL9c477ygwMFAFBQWSpLZt28put8tms2nKlCl67LHH1KdPH/Xt21fLli3TZ599prfeest1nOHDh+umm25SUlKSJCk5OVnjxo3T1Vdfrf79+2vhwoUqKSlxXeYGAAAAwJpMDTiLFi2SJA0bNsytfcmSJRo/frwkadKkSTp9+rQmT56s77//Xn369FFGRoa6du3q6p+fn69vv/3WtX3bbbfp+PHjmjVrlgoKCtS3b1+lp6crNDS00c8JAAAAgHlMDTi1vYHbtGnTavz+mi+//LJKW1JSkmtFBwAAAEDLYOpncAAAAACgIRFwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZRBwAAAAAFgGAQcAAACAZZgacFJTU9WvXz8FBgbK4XAoISFBeXl5bn2GDRsmm83m9nPvvffWeNzx48dXec6oUaMa81QAAAAAeAAfM188OztbiYmJ6tevn8rLyzVjxgzFx8frk08+UUBAgKvfn//8Z82ePdu17e/vf95jjxo1SkuWLHFt+/n5NWzxAAAAADyOqQEnPT3dbXvp0qVyOBzKycnR0KFDXe3+/v4KCwur07H9/Pzq/BwAAAAAzZupAeeXioqKJEkdOnRwa3/99df12muvKSwsTDfeeKNmzpx53lWcrKwsORwOtW/fXtddd53mzJmj4ODgavuWlZWprKzMtV1cXCxJcjqdcjqdF3JK9VZeXu567HQ65fQxpw6rOzu/Zs0zasb8mIex9wzMg3kYe8/BXJjLU8a/Lq9vMwzDaMRaaq2yslKjR4/WiRMntHnzZlf7Sy+9pKioKEVERGjPnj1KSUlR//79tWrVqnMea8WKFfL391d0dLTy8/M1Y8YMtWnTRtu2bZO3t3eV/o8//rieeOKJKu3Lly+v1eVwjeGMcUazi366LG9W21lqZWtlSh0AAACA2UpLSzV27FgVFRUpKCioxr4eE3Duu+8+vffee9q8ebM6dep0zn4bN27U8OHDdeDAAXXt2rVWx/7iiy/UtWtXZWZmavjw4VX2V7eCExkZqW+//fa8A9hYTpWf0qA3B0mSsm7KUpDdnDqszul0KiMjQyNGjJCvr6/Z5eAXmB/zMPaegXkwD2PvOZgLc3nK+BcXFyskJKRWAccjLlFLSkrSmjVr9P7779cYbiQpNjZWkuoUcLp06aKQkBAdOHCg2oDj5+dX7U0IfH19TZtIp/6zDGdmHS0FY+zZmB/zMPaegXkwD2PvOZgLc5k9/nV5bVMDjmEYmjhxotLS0pSVlaXo6OjzPmf37t2SpPDw8Fq/zjfffKPvvvuuTs8BAAAA0PyY+j04iYmJeu2117R8+XIFBgaqoKBABQUFOnXqlCQpPz9fTz75pHJycvTll19q9erVuvPOOzV06FD17t3bdZyePXsqLS1NknTy5ElNmTJF27dv15dffqkNGzZozJgx6tatm0aOHGnKeQIAAABoGqau4CxatEjST1/m+XNLlizR+PHj1apVK2VmZmrhwoUqKSlRZGSkbr75Zj366KNu/fPy8lx3YPP29taePXu0bNkynThxQhEREYqPj9eTTz7Jd+EAAAAAFmf6JWo1iYyMVHZ2dp2OY7fbtW7duguuDQAAAEDzY+olagAAAADQkAg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4HqqissL1OLcw120bAAAAQPUIOB4o81CmElYnuLYnZk3UyH+OVOahTPOKAgAAAJoBAo6HyTyUqeSsZBWWFrq1F5YWKjkrmZADAAAA1ICA40EqKis0d+dcGTKq7DvbNm/nPC5XAwAAAM6BgONBcgtzdaz02Dn3GzJUUFqg3MLcJqwKAAAAaD4IOB7keOnxBu0HAAAAtDQEHA/S0b9jg/YDAAAAWhoCjgeJccQo1D9UNtmq3W+TTWH+YYpxxDRxZQAAAEDzQMDxIN5e3prWf1q1+86GnpT+KfL28m7KsgAAAIBmg4DjYeKi4rRg2AI5/B1u7aH+oVowbIHiouJMqgwAAADwfD5mF4Cq4qLiFBsWq4ErBkqSnh/2vIZEDmHlBgAAADgPVnA81M/DTIwjhnADAAAA1AIBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWAYBBwAAAIBlEHAAAAAAWIaP2QUAZil1lip2eawk6drya+Xr62tyRQAAALhQrOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAxTA05qaqr69eunwMBAORwOJSQkKC8vz63PsGHDZLPZ3H7uvffeGo9rGIZmzZql8PBw2e12xcXFaf/+/Y15KgAAAAA8gKkBJzs7W4mJidq+fbsyMjLkdDoVHx+vkpISt35//vOfdfToUdfP/Pnzazzu/Pnz9dxzz2nx4sXasWOHAgICNHLkSJ0+fboxTwcAAACAyXzMfPH09HS37aVLl8rhcCgnJ0dDhw51tfv7+yssLKxWxzQMQwsXLtSjjz6qMWPGSJJeeeUVhYaG6u2339bvfve7Ks8pKytTWVmZa7u4uFiS5HQ65XQ663xeDaG8vNz12Ol0yuljTh1Wxhh7vrO/f2b9HrZkjL1nYB7Mw9h7DubCXJ4y/nV5fVMDzi8VFRVJkjp06ODW/vrrr+u1115TWFiYbrzxRs2cOVP+/v7VHuPgwYMqKChQXFycq61t27aKjY3Vtm3bqg04qampeuKJJ6q0r1+//pyv09jOGGdcjzdu3KhWtlam1GFljHHzkZGRYXYJLRZj7xmYB/Mw9p6DuTCX2eNfWlpa6742wzCMRqyl1iorKzV69GidOHFCmzdvdrW/9NJLioqKUkREhPbs2aOUlBT1799fq1atqvY4W7du1aBBg3TkyBGFh4e72m+99VbZbDatXLmyynOqW8GJjIzUt99+q6CgoAY8y9o7VX5Kg94cJEnKuilLQXZz6rAyxtjzOZ1OZWRkaMSIEfL19TW7nBaFsfcMzIN5GHvPwVyYy1PGv7i4WCEhISoqKjrv+3OPWcFJTEzUvn373MKNJE2YMMH1+IorrlB4eLiGDx+u/Px8de3atUFe28/PT35+flXafX19TZtIp/6zDGdmHVbGGDcfzI95GHvPwDyYh7H3HMyFucwe/7q8dr1vMnD05FHlHMvRlsNb9Ml3n+hMxZnzP+kckpKStGbNGm3atEmdOnWqsW9sbKwk6cCBA9XuP/tZnWPHjrm1Hzt2rNaf4wEAAADQPNVpBefwycNambdS6QfTdaz0mH5+dZuvl69iQmP020t+qxFRI+RlO392MgxDEydOVFpamrKyshQdHX3e5+zevVuS3C4/+7no6GiFhYVpw4YN6tu3r6SflrR27Nih++677/wnCQAAAKDZqnXASd2RqtX5qzUwYqAmXjlRvUJ6yeHvkJ+3n4rKinTgxAHlHsvVC7tf0OKPF+vJQU+qV0ivGo+ZmJio5cuX65133lFgYKAKCgok/XRTALvdrvz8fC1fvlzXX3+9goODtWfPHk2ePFlDhw5V7969Xcfp2bOnUlNTddNNN8lms2nSpEmaM2eOunfvrujoaM2cOVMRERFKSEio3ygBAAAAaBZqHXDsPna991/vqV3rdlX2BduDFWwPVmx4rO7re582H96sgpKC8wacRYsWSfrpyzx/bsmSJRo/frxatWqlzMxMLVy4UCUlJYqMjNTNN9+sRx991K1/Xl6e6w5skjR16lSVlJRowoQJOnHihAYPHqz09HS1bt26tqcLAAAAoBmqdcCZdNWkWh908EWDa9XvfDdwi4yMVHZ2dp2PY7PZNHv2bM2ePbtWdQAAAACwhnrdZOB0+WmdKj/l2j5y8ohe/eRVbTm8pcEKAwAAAIC6qlfAeWDjA/pX/r8kScVnijX23bFa9u9lenDTg1r5WdXvmQEAAACAplCvgPPp958qxhEjScr4MkPB9mCt/+16PTX4Kb3+2esNWiDQWCoqK1yPcwtz3bYBAADQPNX7ErUA3wBJ0tYjWxXXOU5eNi/16dhHR08ebdACgcaQeShTCasTXNsTsyZq5D9HKvNQpnlFAQAA4ILVK+BEBkVq49cbVVBSoK1HtmpAxABJ0nenv3MFH8BTZR7KVHJWsgpLC93aC0sLlZyVTMgBAABoxuoVcO7tfa+e/vBpjfznSF0RcoX6OvpKkrYd2aaewT0bsj6gQVVUVmjuzrkyVPUOfmfb5u2cx+VqAAAAzVStbxP9c/EXxysmNEbHS4+rR4cervbYsFhd1/m6BisOaGi5hbk6VnrsnPsNGSooLVBuYa76hfVrwsoAAADQEOoVcCQpxB6iEHuIW9sVHa+44IKAxnS89HiD9gMAAIBnqfUlarO3zVZBSUGt+qYfTNeaL9bUuyigsXT079ig/dB4Sp2lilkeo0dPPOr2vVsAAAA1qfUKTvvW7XXTOzepr6OvhnUapstDLldHe0f5efup+Eyx8k/k66PCj/Tel+/JYXdo1oBZjVk3UC8xjhiF+oeqsLSw2s/h2GRTqH+o6zboAAAAaF5qHXAmXjlRt/e8Xav2r9KKvBX6YucXbvsDfAL0q4hf6bEBj2nwRYMbvFCgIXh7eWta/2lKzkquss8mmyQppX+KvL28m7o0AAAANIA6fQYnxB6iCb0naELvCSoqK1JBSYFOV5xWe7/2igyMlM1ma6w6gQYTFxWnBcMWKHVnqtutokP9Q5XSP0VxUXEmVgcAAIALUe+bDLT1a6u2fm0bshagycRFxSk2LFYDVwyUJD0/7HkNiRzCyg0AAEAzV6/vwQGs4OdhJsYRQ7gBAACwAAIOAAAAAMsg4AAAAACwDAIOAAAAAMuoV8A5XX7a7Yv3jpw8olc/eVVbD29tsMIAAAAAoK7qFXAe2PiA/pX/L0lS8ZlijX13rJb9e5ke2PSAVn62skELBAAAAIDaqlfA+fT7T13f9J7xZYaC7cFa/9v1emrwU3r9s9cbtEAAAAAAqK16X6IW4BsgSdp6ZKviOsfJy+alPh376OjJow1aIAAAAADUVr0CTmRQpDZ+vVEFJQXaemSrBkQMkCR9d/o7V/ABAAAAgKZWr4Bzb+979fSHT2vkP0eqV0gv9XX0lSRtO7JNPYN7NmR9AAAAAFBrPvV5UvzF8YoJjdHx0uPq0aGHqz02LFbXdb6uwYoD0HJVVFa4HucW5mpI5BB5e3mbWBEAAGgO6v09OCH2EAX4BmjbkW06XX5aktQrpJe6tO3SYMUBaJkyD2UqYXWCa3ti1kSN/OdIZR7KNK8oAADQLNQr4Jw4fUJ/Wvcn3ZB2g+7fcL+OnzouSZq1dZb+uuuvDVoggJYl81CmkrOSVVha6NZeWFqo5KxkQg4AAKhRvQLO/F3z5ePlo/W/Xa/W3q1d7aMuHqUth7c0WHEAWpaKygrN3TlXhowq+862zds5z+3yNQAAgJ+rV8DZemSrJl81WWEBYW7tnYM660jJkQYpDEDLk1uYq2Olx86535ChgtIC5RbmNmFVAACgOalXwDlVfkqtfVpXaS8uK1Yr71YXXBSAlul46fEG7QcAAFqeegWcmNAYrc5f7dq2yaZKo1Iv73tZ/cP6N1hxAFqWjv4dG7QfANRHqbNUMctj9OiJR3Wq/JTZ5QCoo3rdJjr5qmT9af2f9O/v/i1npVMLchYo/0S+isqK9OqvX23oGgG0EDGOGIX6h6qwtLDaz+HYZFOof6hiHDEmVAcAAJqDeq3gdG/fXWtuWqMYR4yujbxWp8pPaXjn4fq/G/9PkUGRDV0jgBbC28tb0/pPq3afTTZJUkr/FL4Pp5Hxv9cAgOasXis4khTYKlATek9oyFqAJuXv66/csblau3at7D52s8vB/xcXFacFwxYodWeq262iQ/1DldI/RXFRcSZWBwAAPF29A05ZRZk+//5zfX/6e1UalW77ru187QUXBqDliouKU2xYrAauGChJen7Y8xoSOYSVGwAAcF71CjibD2/WI5sf0Q+nf6iyz2az6eM7P77gwlo6VhfQ0v08zMQ4Ygg3AACgVuoVcFJ3pGpE1Ajd2+dehdhDGromAAAAAKiXet1k4LvT32ncZeMINwAAAAA8Sr0CzoioEdp1bFdD1wIAAAAAF6Rel6jNiJ2hh7IeUs6xHF3S/hL5eLkf5o5L72iQ4gAAAACgLuoVcN47+J62HdmmVt6t9GHBh7LZbG77CTgAAAAAzFCvgPNc7nO6v+/9uvuKu+Vlq9dVbgAAAADQ4OqVTpyVTo26eBThBgAAAIBHqVdCGd11tNK/TG/oWgAAHqCissL1OLcw120bAABPV69L1CqNSi3Zt0Rbjmyp9iYDU/tNbZDiAABNK/NQplJ3prq2J2ZNVKh/qKb1n6a4qDgTK2t5Sp2lil0eK0m6tvxa+fr6mlwRADQP9Qo4+0/sV8/gnpKkAycOuO2zyVbdUwAAHi7zUKaSs5JlyHBrLywtVHJWshYMW0DIAQB4vHoFnJdHvtzQdQAATFRRWaG5O+dWCTeSZMiQTTbN2zlP10ZeK28vbxMqBACgdrhLAABAuYW5OlZ67Jz7DRkqKC1QbmFuE1YFAEDd1XoFZ9KmSZozaI7atGqjSZsm1dh34bULL7AsAEBTOl56vEH7AQBglloHnDa+bVxf6BngG8BnbQA0Kn9ff+WOzdXatWtl97GbXY7ldfTv2KD9AAAwS60DzpzBc1yPnxr8VIO8eGpqqlatWqXPPvtMdrtdAwcO1Lx589SjR48qfQ3D0PXXX6/09HSlpaUpISHhnMcdP368li1b5tY2cuRIpadza2sAqE6MI0ah/qEqLC2s9nM4NtkU6h+qGEeMCdUBAFB79foMzt3r7lbxmeIq7SfPnNTd6+6u9XGys7OVmJio7du3KyMjQ06nU/Hx8SopKanSd+HCha4VpNoYNWqUjh496vp54403av1cAGhpvL28Na3/tGr3nV2xT+mfwg0GAAAer153UdtVsEvOCmeV9rKKMuUeq/0HUH+5orJ06VI5HA7l5ORo6NChrvbdu3frmWee0Ycffqjw8PBaHdvPz09hYWG16ltWVqaysjLXdnHxT+HN6XTK6ax6nk3l7GubWYPVMcaejflpWtdEXKP5Q+Zr/ofzdfzUfz5r4/B36OGrHtY1EdcwF02ovLzc9djpdMrpw9g3Fcbes/Bvgbk8Zfzr8vp1Cjh53+e5Hn9R9IW+PfWta7vSqNSWI1vk8HfU5ZBuioqKJEkdOnRwtZWWlmrs2LF64YUXah1YJCkrK0sOh0Pt27fXddddpzlz5ig4OLjavqmpqXriiSeqtK9fv17+/v51PIuGl5GRYXYJlscYezbmp2nd43uP5pz66bLkOwPuVDefbirbW6a1e9eaXFnLcsY443q8ceNGtbK1MrGaloWx90z8W2Aus8e/tLS01n1thmFUvdj6HHov6+26TKy6p7X2aa3p/afrpu431bqAsyorKzV69GidOHFCmzdvdrXfc889qqio0D/+8Y+fCrbZzvsZnBUrVsjf31/R0dHKz8/XjBkz1KZNG23btk3e3lUvr6huBScyMlLffvutgoKC6nwuDcXpdCojI0MjRozgG6wbCWPs2Zgfc5wqP6VBbw6SJGXdlKUgu3l/B1sy5sE8jL1n4d8Cc3nK+BcXFyskJERFRUXnfX9epxWc9JvTZcjQr//5a73xmzfUvnV71z5fL191aN2h3tdnJyYmat++fW7hZvXq1dq4caM++uijOh3rd7/7nevxFVdcod69e6tr167KysrS8OHDq/T38/OTn59flXZfX1+P+EXylDqsjDH2bMxP03LqP5cBMPbmOV152vV47w97NaTNED4D1UT4HfBMzIW5zB7/urx2nW4yENEmQhe1uUh7xu3R5SGXK6JNhOuno3/Hev/hTUpK0po1a7Rp0yZ16tTJ1b5x40bl5+erXbt28vHxkY/PT3ns5ptv1rBhw2p9/C5duigkJEQHDhyoV30AADSlzEOZSlid4NqemDVRI/85UpmHMs0rCgCaiXrdRa2hGIahpKQkpaWlaePGjYqOjnbbP23aNO3Zs0e7d+92/UjS3/72Ny1ZsqTWr/PNN9/ou+++q/UNCgAAMEvmoUwlZyWrsLTQrb2wtFDJWcmEnCZQUVnhepxbmOu2DcDzmRpwEhMT9dprr2n58uUKDAxUQUGBCgoKdOrUKUlSWFiYevXq5fYjSZ07d3YLQz179lRaWpok6eTJk5oyZYq2b9+uL7/8Uhs2bNCYMWPUrVs3jRw5sulPEgCAWqqorNDcnXOr/S6is23zds7jDXcjYvUMaP5MDTiLFi1SUVGRhg0bpvDwcNfPypUr63ScvLw81x3YvL29tWfPHo0ePVqXXHKJ7r77bl111VX64IMPqv2cDQAAniK3MFfHSo+dc78hQwWlBcotrP1XMqD2WD0DrKFe34PTUOpwA7can/PzNrvdrnXr1l1QXQAAmOF46fHzd6pDP9Te+VbPbLJp3s55ujbyWm72AHg4U1dwAADAf3T079ig/VB7rJ4B1lHrFZyBbwyUTbZa9d1y+5Z6FwQAQEsV44hRqH+oCksLq11JsMmmUP9QxThiTKjO2lg9A6yj1gEnpV+K6/GJshN6ac9LGhQxSH0cfSRJHxd+rC1Htuie3vc0fJUAgCbj7+uv3LG5Wrt2rew+drPLaVG8vbw1rf80JWclV9l39j8ZU/qncIlUI2D1DLCOWgecMd3GuB5P3jRZiX0TNfbSsa62Oy69Q8s/Xa7tR7frzsvvbNgqAQBoIeKi4rRg2AKl7kx1+7B7qH+oUvqnKC4qzsTqrIvVM8A66vUZnC1HtmjwRYOrtA++aLC2H91+wUUBANCSxUXF6e3Rb7u2nx/2vNJvTifcNKKzq2fVYfUMaF7qFXDa+bXTpq83VWnf9PUmtfNrd6E1AQDQ4v38jXSMI4Y31k3g7OqZw9/h1h7qH6oFwxYQMIFmol63ib6/7/16fOvj2lWwS1eEXCFJ2vvtXm05vEWPDXysQQsEAABoKnFRcYoNi9XAFQMl/bR6NiRyCAETaEbqFXASuiWoS9suev3T17Xhqw2SpOi20Vr262Xq3bF3gxYIAADQlFg9A5q3en/RZ++OvQkzAAAAADxKrQPOyTMna33QNq3a1KsYAAAAALgQdfuiT1vNX/RpGIZsNps+vvPjCy4MAAAAAOqq1gHnf0f+b2PWAQAAAAAXrNYBp19Yv8asAwAAAAAuWK0DTt73eerevru8bF7K+z6vxr49OvS44MIAAAAAoK5qHXBu+dct2nTrJgXbg3XLv26RzWaTYRhV+vEZHAAAAABmqXXASb85XR1ad3A9BgAAjcff11+5Y3O1du1a2X3sZpcDAM1GrQNORJuIah8DAAAAgKeo1xd9rs5fXeP+0V1H16sYAAAAALgQ9Qo4c3fOddsuryzX6fLT8vXyVWuf1gQcAAAAAKaoV8DZevvWKm2Hig/pye1P6q7L77rgogAAAACgPrwa6kBRQVGaHDO5yuoOAAAAADSVBgs4kuTt5a3jp4435CEBAAAAoNbqdYnapq82uW0bMvTtqW/1xmdvqK+jb0PUBQAAAAB1Vq+A8+CmB922bTab2vu1V//w/ppy9ZQGKQwAAAAA6qpeAWfPuD0NXQcAAAAAXLAL/gyOYRgyDKMhagEAAACAC1KvFRxJWrV/lV795FUdKj4k6ae7qP3+0t/r5ktubrDiAAAAAKAu6hVw/vuj/9Yrn7yisT3Hqk/HPpKkj49/rPm75utoyVElXZnUoEUCAACg5Sl1lip2eawk6drya+Xr62tyRWgO6hVw3sx7U48PeFzXd7ne1XZt52t1SftLlLozlYADAAAAwBT1+gxOeWW5Lg+5vEr7ZcGXqaKy4oKLAgAAAID6qFfAuaHrDVqZt7JK+1ufv+W2qgMAAAAATanWl6jN3zXf9dgmm1btX6VtR7apd8fekqQ9x/eooKRAN3a9seGrBAAAAIBaqHXA+ez7z9y2Lwu+TJL09Y9fS5Lat26v9q3bK/9EfgOWBwAAAAC1V+uA8/LIlxuzDgAAAI/g7+uv3LG5Wrt2rew+drPLAVBHF/xFnwAAAADgKQg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACzD1ICTmpqqfv36KTAwUA6HQwkJCcrLy6u2r2EY+vWvfy2bzaa33367xuMahqFZs2YpPDxcdrtdcXFx2r9/fyOcAQAAAABPYmrAyc7OVmJiorZv366MjAw5nU7Fx8erpKSkSt+FCxfKZrPV6rjz58/Xc889p8WLF2vHjh0KCAjQyJEjdfr06YY+BQAAAAAexMfMF09PT3fbXrp0qRwOh3JycjR06FBX++7du/XMM8/oww8/VHh4eI3HNAxDCxcu1KOPPqoxY8ZIkl555RWFhobq7bff1u9+97uGPxEAAAAAHsHUgPNLRUVFkqQOHTq42kpLSzV27Fi98MILCgsLO+8xDh48qIKCAsXFxbna2rZtq9jYWG3btq3agFNWVqaysjLXdnFxsSTJ6XTK6XTW+3wu1NnXNrMGq2OMPRvzYx7G3jMwD+Zh7D1DeXm567HT6ZTTh/loap7yu1CX1/eYgFNZWalJkyZp0KBB6tWrl6t98uTJGjhwoGs15nwKCgokSaGhoW7toaGhrn2/lJqaqieeeKJK+/r16+Xv71/bU2g0GRkZZpdgeYyxZ2N+zMPYewbmwTyMvblOV/7n4wUvr39Z3Xy6ycvGPbLMYPbvQmlpaa37ekzASUxM1L59+7R582ZX2+rVq7Vx40Z99NFHjfra06dPV3Jysmu7uLhYkZGRio+PV1BQUKO+dk2cTqcyMjI0YsQI+fr6mlaHlTHGno35MQ9j7xmYB/Mw9ubb8PUGPfvhs67tV0pekcPfoSlXTdHwyOEmVtayeMrvwtkrrGrDIwJOUlKS1qxZo/fff1+dOnVytW/cuFH5+flq166dW/+bb75ZQ4YMUVZWVpVjnb2M7dixY26f1zl27Jj69u1b7ev7+fnJz8+vSruvr69H/FHzlDqsjDH2bMyPeRh7z8A8mIexN0fmoUxN/WCqDBlu7cdLj2vqB1O1YNgCxUXFnePZaAxm/y7U5bVNXeMzDENJSUlKS0vTxo0bFR0d7bZ/2rRp2rNnj3bv3u36kaS//e1vWrJkSbXHjI6OVlhYmDZs2OBqKy4u1o4dOzRgwIBGOxcAAABcuIrKCs3dObdKuJHkapu3c54qKiuaujQ0E6au4CQmJmr58uV65513FBgY6PqMTNu2bWW32xUWFlbtjQU6d+7sFoZ69uyp1NRU3XTTTbLZbJo0aZLmzJmj7t27Kzo6WjNnzlRERIQSEhKa6tQAAABQD7mFuTpWeuyc+w0ZKigtUG5hrvqF9WvCytBcmBpwFi1aJEkaNmyYW/uSJUs0fvz4Wh8nLy/PdQc2SZo6dapKSko0YcIEnThxQoMHD1Z6erpat27dEGUDAACgkRwvPd6g/dDymBpwDKPq0mN9nvPLNpvNptmzZ2v27Nn1rg0AAABNr6N/xwbth5aH++wBAADAY8Q4YhTqHyqbbNXut8mmMP8wxThimrgyNBcEHAAAAHgMby9vTes/rdp9Z0NPSv8UeXt5N2VZaEYIOAAAAPAocVFxWjBsgRz+Drf2UP9QbhGN8/KI78EBAAAAfi4uKk6xYbEauGKgJOn5Yc9rSOQQVm5wXqzgAAAAwCP9PMzEOGIIN6gVAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMH7MLAAAAAKrj7+uv3LG5Wrt2rew+drPLQTPBCg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMbjIAAAAAoIpSZ6lil8dKkq4tv1a+vr4mV1Q7rOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLMDXgpKamql+/fgoMDJTD4VBCQoLy8vLc+txzzz3q2rWr7Ha7OnbsqDFjxuizzz6r8bjjx4+XzWZz+xk1alRjngoAAAAAD2BqwMnOzlZiYqK2b9+ujIwMOZ1OxcfHq6SkxNXnqquu0pIlS/Tpp59q3bp1MgxD8fHxqqioqPHYo0aN0tGjR10/b7zxRmOfDgAAAACT+Zj54unp6W7bS5culcPhUE5OjoYOHSpJmjBhgmv/xRdfrDlz5qhPnz768ssv1bVr13Me28/PT2FhYY1TOAAAAACPZGrA+aWioiJJUocOHardX1JSoiVLlig6OlqRkZE1HisrK0sOh0Pt27fXddddpzlz5ig4OLjavmVlZSorK3NtFxcXS5KcTqecTmd9TqVBnH1tM2uwOsbYszE/5mHsPQPzYB7G3nMwF+YpLy93PXY6nXL6mP++uDZshmEYjVhLrVVWVmr06NE6ceKENm/e7LbvxRdf1NSpU1VSUqIePXro3XffrXH1ZsWKFfL391d0dLTy8/M1Y8YMtWnTRtu2bZO3t3eV/o8//rieeOKJKu3Lly+Xv7//hZ8cAAAA0MycMc5odtFsSdKstrPUytbKtFpKS0s1duxYFRUVKSgoqMa+HhNw7rvvPr333nvavHmzOnXq5LavqKhIhYWFOnr0qJ5++mkdPnxYW7ZsUevWrWt17C+++EJdu3ZVZmamhg8fXmV/dSs4kZGR+vbbb887gI3J6XQqIyNDI0aMkK+vr2l1WBlj7NmYH/Mw9p6BeTAPY+85mAvznCo/pUFvDpIkZd2UpSC7ee+Li4uLFRISUquA4xGXqCUlJWnNmjV6//33q4QbSWrbtq3atm2r7t2761e/+pXat2+vtLQ03X777bU6fpcuXRQSEqIDBw5UG3D8/Pzk5+dXpd3X19cjfpE8pQ4rY4w9G/NjHsbeMzAP5mHsPQdz0fSc+s9lYWaPf11e29SAYxiGJk6cqLS0NGVlZSk6OrpWzzEMw23F5Xy++eYbfffddwoPD7+QcgEAAAB4OFNvE52YmKjXXntNy5cvV2BgoAoKClRQUKBTp05J+unSstTUVOXk5Oirr77S1q1bdcstt8hut+v66693Hadnz55KS0uTJJ08eVJTpkzR9u3b9eWXX2rDhg0aM2aMunXrppEjR5pyngAAAEBzU1H5n69lyS3Mddv2ZKYGnEWLFqmoqEjDhg1TeHi462flypWSpNatW+uDDz7Q9ddfr27duum2225TYGCgtm7dKofD4TpOXl6e6w5s3t7e2rNnj0aPHq1LLrlEd999t6666ip98MEH1V6GBgAAAMBd5qFMJaxOcG1PzJqokf8cqcxDmeYVVUumX6JWk4iICK1du7ZOx7Hb7Vq3bt0F1wYAAAC0RJmHMpWclSxD7u/VC0sLlZyVrAXDFiguKs6k6s7P1BUcAAAAAJ6jorJCc3fOrRJuJLna5u2c59GXqxFwAAAAAEj66bM2x0qPnXO/IUMFpQXKLcxtwqrqhoADAAAAQJJ0vPR4g/YzAwEHAAAAgCSpo3/HBu1nBgIOAAAAAElSjCNGof6hsslW7X6bbArzD1OMI6aJK6s9Ag4AAAAASZK3l7em9Z9W7b6zoSelf4q8vbybsqw6IeAAAAAAcImLitOCYQvk8He4tYf6h3r8LaIlk78HBwAAAIDniYuKU2xYrAauGChJen7Y8xoSOcSjV27OYgUHAAAAQBU/DzMxjphmEW4kAg4AAAAACyHgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMH7MLAAAAAOB5/H39lTs2V2vXrpXdx252ObXGCg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAyyDgAAAAALAMAg4AAAAAy/AxuwBPZBiGJKm4uNjUOpxOp0pLS1VcXCxfX19Ta7EqxtizMT/mYew9A/NgHsbeczAX5vKU8T/7vvzs+/SaEHCq8eOPP0qSIiMjTa4EAAAAwFk//vij2rZtW2Mfm1GbGNTCVFZW6siRIwoMDJTNZjOtjuLiYkVGRurrr79WUFCQaXWYoV+/ftq1a1ejv05LHuPG1hBz2JLnp6l+B87FzLE3+9wbSnP6HfDUMTezrpb898fTMBfmMmP8q/vdNwxDP/74oyIiIuTlVfOnbFjBqYaXl5c6depkdhkuQUFBLe4X2tvbu0nPuSWOcWNryDlsifPT1L8D52LG2HvKuV+o5vQ74Klj7gl1tcS/P56KuTBXU47/uX73z7dycxY3GYBHSkxMNLsEXCDm8MK05PGzyrk3p/Pw1Fo9tS4AjetCf/e5RM2DFRcXq23btioqKuJ/LBoJY+zZmB/zMPaegXkwD2PvOZgLczXH8WcFx4P5+fnpsccek5+fn9mlWBZj7NmYH/Mw9p6BeTAPY+85mAtzNcfxZwUHAAAAgGWwggMAAADAMgg4AAAAACyDgAMAAADAMgg4AAAAACyDgOMB3n//fd14442KiIiQzWbT22+/XaXPp59+qtGjR6tt27YKCAhQv3799NVXXzV9sc1Qamqq+vXrp8DAQDkcDiUkJCgvL8+1//vvv9fEiRPVo0cP2e12de7cWQ888ICKiopMrLrlWLRokXr37u36ArEBAwbovffek8TcNLW5c+fKZrNp0qRJrrZhw4bJZrO5/dx7773mFWlhhw8f1u9//3sFBwfLbrfriiuu0Icfflht33vvvVc2m00LFy5s2iIt6Mcff9SkSZMUFRUlu92ugQMHun2DumEYmjVrlsLDw2W32xUXF6f9+/ebWLE11PTex+l0KiUlRVdccYUCAgIUERGhO++8U0eOHHE7xueff64xY8YoJCREQUFBGjx4sDZt2tTEZ9I8ne+958mTJ5WUlKROnTrJbrfrsssu0+LFi936vPTSSxo2bJiCgoJks9l04sSJpjuB8yDgeICSkhL16dNHL7zwQrX78/PzNXjwYPXs2VNZWVnas2ePZs6cqdatWzdxpc1Tdna2EhMTtX37dmVkZMjpdCo+Pl4lJSWSpCNHjujIkSN6+umntW/fPi1dulTp6em6++67Ta68ZejUqZPmzp2rnJwcffjhh7ruuus0ZswY/fvf/2ZumtCuXbv0P//zP+rdu3eVfX/+85919OhR18/8+fNNqNDafvjhBw0aNEi+vr5677339Mknn+iZZ55R+/btq/RNS0vT9u3bFRERYUKl1vOnP/1JGRkZevXVV7V3717Fx8crLi5Ohw8fliTNnz9fzz33nBYvXqwdO3YoICBAI0eO1OnTp02uvHmr6b1PaWmpcnNzNXPmTOXm5mrVqlXKy8vT6NGj3frdcMMNKi8v18aNG5WTk6M+ffrohhtuUEFBQVOdRrN1vveeycnJSk9P12uvvaZPP/1UkyZNUlJSklavXu3qU1paqlGjRmnGjBlNVXbtGfAokoy0tDS3tttuu834/e9/b05BFlRYWGhIMrKzs8/Z58033zRatWplOJ3OJqwMZ7Vv3974xz/+Ue0+5qbh/fjjj0b37t2NjIwM45prrjEefPBB175fbqNxpKSkGIMHDz5vv2+++ca46KKLjH379hlRUVHG3/72t8YvzsJKS0sNb29vY82aNW7tMTExxiOPPGJUVlYaYWFhxl//+lfXvhMnThh+fn7GG2+80dTlWlZ1731+aefOnYYk49ChQ4ZhGMbx48cNScb777/v6lNcXGxIMjIyMhqzXMupbvwvv/xyY/bs2W5tZ38vfmnTpk2GJOOHH35oxCrrhhUcD1dZWal3331Xl1xyiUaOHCmHw6HY2NhqL2ND7Zy9vKlDhw419gkKCpKPj09TlQVJFRUVWrFihUpKSjRgwIBq+zA3DS8xMVG/+c1vFBcXV+3+119/XSEhIerVq5emT5+u0tLSJq7Q+lavXq2rr75at9xyixwOh6688kr9/e9/d+tTWVmpP/zhD5oyZYouv/xykyq1lvLyclVUVFS5IsJut2vz5s06ePCgCgoK3H432rZtq9jYWG3btq2py23RioqKZLPZ1K5dO0lScHCwevTooVdeeUUlJSUqLy/X//zP/8jhcOiqq64yt1gLGDhwoFavXq3Dhw/LMAxt2rRJn3/+ueLj480urVZ4h+DhCgsLdfLkSc2dO1dz5szRvHnzlJ6erv/6r//Spk2bdM0115hdYrNSWVmpSZMmadCgQerVq1e1fb799ls9+eSTmjBhQhNX13Lt3btXAwYM0OnTp9WmTRulpaXpsssuq9KPuWl4K1asUG5urttnDn5u7NixioqKUkREhPbs2aOUlBTl5eVp1apVTVyptX3xxRdatGiRkpOTNWPGDO3atUsPPPCAWrVqpXHjxkmS5s2bJx8fHz3wwAMmV2sdgYGBGjBggJ588kldeumlCg0N1RtvvKFt27apW7durkudQkND3Z4XGhrKZVBN6PTp00pJSdHtt9+uoKAgSZLNZlNmZqYSEhIUGBgoLy8vORwOpaenV3tpJ+rm+eef14QJE9SpUyf5+PjIy8tLf//73zV06FCzS6sVAo6Hq6yslCSNGTNGkydPliT17dtXW7du1eLFiwk4dZSYmKh9+/Zp8+bN1e4vLi7Wb37zG1122WV6/PHHm7a4FqxHjx7avXu3ioqK9NZbb2ncuHHKzs52CznMTcP7+uuv9eCDDyojI+Ocn+n7eZi84oorFB4eruHDhys/P19du3ZtqlItr7KyUldffbX+8pe/SJKuvPJK7du3T4sXL9a4ceOUk5OjZ599Vrm5ubLZbCZXay2vvvqq/vjHP+qiiy6St7e3YmJidPvttysnJ8fs0qCfbjhw6623yjAMLVq0yNVuGIYSExPlcDj0wQcfyG636x//+IduvPFG7dq1S+Hh4SZW3fw9//zz2r59u1avXq2oqCi9//77SkxMVERExDlX+z0Jl6h5uJCQEPn4+FT53+xLL72Uu6jVUVJSktasWaNNmzapU6dOVfb/+OOPGjVqlAIDA5WWliZfX18TqmyZWrVqpW7duumqq65Samqq+vTpo2effda1n7lpHDk5OSosLFRMTIx8fHzk4+Oj7OxsPffcc/Lx8VFFRUWV58TGxkqSDhw40NTlWlp4eHiNf+c/+OADFRYWqnPnzq65OnTokB566CFdfPHFJlRsHV27dlV2drZOnjypr7/+Wjt37pTT6VSXLl0UFhYmSTp27Jjbc44dO+bah8ZzNtwcOnRIGRkZrtUbSdq4caPWrFmjFStWaNCgQYqJidGLL74ou92uZcuWmVh183fq1CnNmDFDCxYs0I033qjevXsrKSlJt912m55++mmzy6sVVnA8XKtWrdSvXz+32xpLP90aMSoqyqSqmhfDMDRx4kSlpaUpKytL0dHRVfoUFxdr5MiR8vPz0+rVq7lDnckqKytVVlYmiblpTMOHD9fevXvd2u666y717NlTKSkp8vb2rvKc3bt3SxL/O9rABg0aVOPf+T/84Q9V/td05MiR+sMf/qC77rqryeq0soCAAAUEBOiHH37QunXrNH/+fEVHRyssLEwbNmxQ3759Jf30N2nHjh267777zC3Y4s6Gm/3792vTpk0KDg5223/2s4BeXu7/V+/l5eW6+gX143Q65XQ6q4ytt7d3sxlbAo4HOHnypNv/hh48eFC7d+9Whw4d1LlzZ02ZMkW33Xabhg4dqmuvvVbp6en617/+paysLPOKbkYSExO1fPlyvfPOOwoMDHRdN922bVvZ7XYVFxcrPj5epaWleu2111RcXKzi4mJJUseOHat9k4eGM336dP36179W586d9eOPP2r58uXKysrSunXrmJtGFhgYWOWzaAEBAQoODlavXr2Un5+v5cuX6/rrr1dwcLD27NmjyZMna+jQodXeThr1N3nyZA0cOFB/+ctfdOutt2rnzp166aWX9NJLL0n66QPVv3yD5+vrq7CwMPXo0cOMki1j3bp1MgxDPXr00IEDBzRlyhT17NlTd911l+t7oebMmaPu3bsrOjpaM2fOVEREhBISEswuvVmr6b1PeHi4fvvb3yo3N1dr1qxRRUWF69/uDh06qFWrVhowYIDat2+vcePGadasWbLb7fr73/+ugwcP6je/+Y1Zp9VsnO+95zXXXKMpU6bIbrcrKipK2dnZeuWVV7RgwQLXcwoKClRQUOA6zt69exUYGKjOnTvXeCOnJmHqPdxgGMZ/bq/3y59x48a5+vzv//6v0a1bN6N169ZGnz59jLffftu8gpuZ6sZWkrFkyRLDMM49/pKMgwcPmlp7S/DHP/7RiIqKMlq1amV07NjRGD58uLF+/XrDMJgbM/z8ttBfffWVMXToUKNDhw6Gn5+f0a1bN2PKlClGUVGRuUVa1L/+9S+jV69ehp+fn9GzZ0/jpZdeqrE/t4luGCtXrjS6dOlitGrVyggLCzMSExONEydOuPZXVlYaM2fONEJDQw0/Pz9j+PDhRl5enokVW0NN730OHjx4zr/9mzZtch1j165dRnx8vNGhQwcjMDDQ+NWvfmWsXbvWvJNqRs733vPo0aPG+PHjjYiICKN169ZGjx49jGeeecaorKx0HeOxxx6r8f2VmWyGYRiNE50AAAAAoGlxkwEAAAAAlkHAAQAAAGAZBBwAAAAAlkHAAQAAAGAZBBwAAAAAlkHAAQAAAGAZBBwAAAAAlkHAAQAAAGAZBBwAQLMxbNgwTZo06YKPM378eCUkJFzwcQAAnoeAAwColYKCAj344IPq1q2bWrdurdDQUA0aNEiLFi1SaWmp2eUBACBJ8jG7AACA5/viiy80aNAgtWvXTn/5y190xRVXyM/PT3v37tVLL72kiy66SKNHj672uU6nU76+vk1csfkqKipks9nk5cX/JQJAU+KvLgDgvO6//375+Pjoww8/1K233qpLL71UXbp00ZgxY/Tuu+/qxhtvdPW12WxatGiRRo8erYCAAD311FOqqKjQ3XffrejoaNntdvXo0UPPPvus22ucvWzsiSeeUMeOHRUUFKR7771XZ86ccetXWVmpqVOnqkOHDgoLC9Pjjz9eY+0VFRVKTk5Wu3btFBwcrKlTp8owjCrHTE1NddXXp08fvfXWW259Vq9ere7du6t169a69tprtWzZMtlsNp04cUKStHTpUrVr106rV6/WZZddJj8/P3311VcqKyvTww8/rIsuukgBAQGKjY1VVlaW27E3b96sIUOGyG63KzIyUg888IBKSkpqMTMAgF8i4AAAavTdd99p/fr1SkxMVEBAQLV9bDab2/bjjz+um266SXv37tUf//hHVVZWqlOnTvq///s/ffLJJ5o1a5ZmzJihN9980+15GzZs0KeffqqsrCy98cYbWrVqlZ544gm3PsuWLVNAQIB27Nih+fPna/bs2crIyDhn/c8884yWLl2ql19+WZs3b9b333+vtLQ0tz6pqal65ZVXtHjxYv373//W5MmT9fvf/17Z2dmSpIMHD+q3v/2tEhIS9PHHH+uee+7RI488UuW1SktLNW/ePP3jH//Qv//9bzkcDiUlJWnbtm1asWKF9uzZo1tuuUWjRo3S/v37JUn5+fkaNWqUbr75Zu3Zs0crV67U5s2blZSUdM5zAgDUwAAAoAbbt283JBmrVq1yaw8ODjYCAgKMgIAAY+rUqa52ScakSZPOe9zExETj5ptvdm2PGzfO6NChg1FSUuJqW7RokdGmTRujoqLCMAzDuOaaa4zBgwe7Hadfv35GSkrKOV8nPDzcmD9/vmvb6XQanTp1MsaMGWMYhmGcPn3a8Pf3N7Zu3er2vLvvvtu4/fbbDcMwjJSUFKNXr15u+x955BFDkvHDDz8YhmEYS5YsMSQZu3fvdvU5dOiQ4e3tbRw+fNjtucOHDzemT5/uep0JEya47f/ggw8MLy8v49SpU+c8LwBA9fgMDgCgXnbu3KnKykrdcccdKisrc9t39dVXV+n/wgsv6OWXX9ZXX32lU6dO6cyZM+rbt69bnz59+sjf39+1PWDAAJ08eVJff/21oqKiJEm9e/d2e054eLgKCwurrbGoqEhHjx5VbGysq83Hx0dXX3216zK1AwcOqLS0VCNGjHB77pkzZ3TllVdKkvLy8tSvXz+3/f3796/yeq1atXKrb+/evaqoqNAll1zi1q+srEzBwcGSpI8//lh79uzR66+/7tpvGIYqKyt18OBBXXrppdWeGwCgegQcAECNunXrJpvNpry8PLf2Ll26SJLsdnuV5/zyUrYVK1bo4Ycf1jPPPKMBAwYoMDBQf/3rX7Vjx4461/PLGxbYbDZVVlbW+ThnnTx5UpL07rvv6qKLLnLb5+fnV6dj2e12t8v1Tp48KW9vb+Xk5Mjb29utb5s2bVx97rnnHj3wwANVjte5c+c6vT4AgIADADiP4OBgjRgxQv/93/+tiRMnnvNzODXZsmWLBg4cqPvvv9/Vlp+fX6Xfxx9/rFOnTrlC0/bt29WmTRtFRkbWq/a2bdsqPDxcO3bs0NChQyVJ5eXlysnJUUxMjCS53RDgmmuuqfY4PXr00Nq1a93adu3add7Xv/LKK1VRUaHCwkINGTKk2j4xMTH65JNP1K1bt7qcGgDgHLjJAADgvF588UWVl5fr6quv1sqVK/Xpp58qLy9Pr732mj777LMqqxO/1L17d3344Ydat26dPv/8c82cObPagHDmzBndfffd+uSTT7R27Vo99thjSkpKuqBbLT/44IOaO3eu3n77bX322We6//77XXc+k6TAwEA9/PDDmjx5spYtW6b8/Hzl5ubq+eef17JlyyRJ99xzjz777DOlpKTo888/15tvvqmlS5dKqnqDhZ+75JJLdMcdd+jOO+/UqlWrdPDgQe3cuVOpqal69913JUkpKSnaunWrkpKStHv3bu3fv1/vvPMONxkAgHpiBQcAcF5du3bVRx99pL/85S+aPn26vvnmG/n5+emyyy7Tww8/7LYyU5177rlHH330kW677TbZbDbdfvvtuv/++/Xee++59Rs+fLi6d++uoUOHqqysTLfffvt5bwN9Pg899JCOHj2qcePGycvLS3/84x910003qaioyNXnySefVMeOHZWamqovvvhC7dq1U0xMjGbMmCFJio6O1ltvvaWHHnpIzz77rAYMGKBHHnlE991333kvY1uyZInmzJmjhx56SIcPH1ZISIh+9atf6YYbbpD002eKsrOz9cgjj2jIkCEyDENdu3bVbbfddkHnDQAtlc0wfvFlAAAAmGD8+PE6ceKE3n77bbNLqZWnnnpKixcv1tdff212KQCAn2EFBwCAWnjxxRfVr18/BQcHa8uWLfrrX//KZWQA4IEIOAAA1ML+/fs1Z84cff/99+rcubMeeughTZ8+3eyyAAC/wCVqAAAAACyDu6gBAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADLIOAAAAAAsAwCDgAAAADL+H8IET2WmBAoPAAAAABJRU5ErkJggg==",
"text/plain": [
"<Figure size 960x480 with 1 Axes>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"\n",
"#index_params = cagra.IndexParams(intermediate_graph_degree=128, graph_degree=64, build_algo=\"nn_descent\", metric=metric)\n",
"\n",
"\n",
"bench_gd = np.exp2(np.arange(4, 8, 0.5)).astype(np.int32)\n",
"bench_avg = np.zeros_like(bench_gd, dtype=np.float32)\n",
"bench_std = np.zeros_like(bench_gd, dtype=np.float32)\n",
"bench_recall = np.zeros_like(bench_gd, dtype=np.float32)\n",
"\n",
"for i, gd in enumerate(bench_gd):\n",
" index_params = cagra.IndexParams(intermediate_graph_degree=200, graph_degree=gd, build_algo=\"nn_descent\", metric=metric)\n",
" build_t = %timeit -o cagra.build(index_params, dataset, handle=resources); resources.sync()\n",
" bench_avg[i] = (queries.shape[0] * build_t.loops / np.array(build_t.all_runs)).mean()\n",
" bench_std[i] = (queries.shape[0] * build_t.loops / np.array(build_t.all_runs)).std()\n",
"\n",
"fig, ax = plt.subplots(1, 1, figsize=plt.figaspect(1/2))\n",
"color = 'tab:green'\n",
"ax.errorbar(bench_gd, bench_avg, bench_std, fmt='o', color=color)\n",
"ax.set_xscale('log')\n",
"ax.set_xticks(bench_gd, bench_gd)\n",
"ax.set_xlabel('Graph degree')\n",
"ax.grid()\n",
"ax.set_ylabel('build times (s)', color=color)\n",
"\n",
"#ax2 = ax.twinx()\n",
"#color = 'tab:pink'\n",
"#ax2.set_ylabel('Recall', color=color)\n",
"#ax2.set_yticks(np.arange(0.5, 1.0, 0.05)+0.05, minor=True)\n",
"#ax2.grid(True, linestyle=\":\")\n",
"#ax2.plot(bench_k, bench_recall, color=color)"
]
},
{
"cell_type": "markdown",
"id": "ebf79ff8",
"metadata": {},
"source": [
"### Build algorithm\n",
"One of the major component of the build step is the algorithm chose for the CAGRA graph initialization.\n",
"- `ivf_pq`. The IVF-PQ option will first build an IVF-PQ index, then initialize the CAGRA graph with the closest neighbors of each node according to IVF-PQ.\n",
"- `nn_descent` is using a Nearest Neighbors Descent algorithm to initialize the CAGRA graph. It is the fastest option."
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "9b39f519",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"15.5 s ± 50.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)\n"
]
},
{
"ename": "NameError",
"evalue": "name 'bench_build_avg' is not defined",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mNameError\u001b[0m Traceback (most recent call last)",
"Cell \u001b[0;32mIn[11], line 7\u001b[0m\n\u001b[1;32m 5\u001b[0m index_params \u001b[38;5;241m=\u001b[39m cagra\u001b[38;5;241m.\u001b[39mIndexParams(intermediate_graph_degree\u001b[38;5;241m=\u001b[39m\u001b[38;5;241m128\u001b[39m, graph_degree\u001b[38;5;241m=\u001b[39m\u001b[38;5;241m32\u001b[39m, build_algo\u001b[38;5;241m=\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mnn_descent\u001b[39m\u001b[38;5;124m\"\u001b[39m, metric\u001b[38;5;241m=\u001b[39mmetric)\n\u001b[1;32m 6\u001b[0m build_t \u001b[38;5;241m=\u001b[39m get_ipython()\u001b[38;5;241m.\u001b[39mrun_line_magic(\u001b[38;5;124m'\u001b[39m\u001b[38;5;124mtimeit\u001b[39m\u001b[38;5;124m'\u001b[39m, \u001b[38;5;124m'\u001b[39m\u001b[38;5;124m-o index = cagra.build(index_params, dataset, handle=resources); resources.sync()\u001b[39m\u001b[38;5;124m'\u001b[39m)\n\u001b[0;32m----> 7\u001b[0m \u001b[43mbench_build_avg\u001b[49m[i] \u001b[38;5;241m=\u001b[39m (queries\u001b[38;5;241m.\u001b[39mshape[\u001b[38;5;241m0\u001b[39m] \u001b[38;5;241m*\u001b[39m build_t\u001b[38;5;241m.\u001b[39mloops \u001b[38;5;241m/\u001b[39m np\u001b[38;5;241m.\u001b[39marray(build_t\u001b[38;5;241m.\u001b[39mall_runs))\u001b[38;5;241m.\u001b[39mmean()\n\u001b[1;32m 8\u001b[0m bench_build_std[i] \u001b[38;5;241m=\u001b[39m (queries\u001b[38;5;241m.\u001b[39mshape[\u001b[38;5;241m0\u001b[39m] \u001b[38;5;241m*\u001b[39m build_t\u001b[38;5;241m.\u001b[39mloops \u001b[38;5;241m/\u001b[39m np\u001b[38;5;241m.\u001b[39marray(build_t\u001b[38;5;241m.\u001b[39mall_runs))\u001b[38;5;241m.\u001b[39mstd()\n\u001b[1;32m 9\u001b[0m \u001b[38;5;66;03m# distances, neighbors = cagra.search(search_params, index, queries, 64, handle=resources); resources.sync()\u001b[39;00m\n\u001b[1;32m 10\u001b[0m \u001b[38;5;66;03m# bench_recall[i] = calc_recall(neighbors, gt_neighbors); resources.sync()\u001b[39;00m\n",
"\u001b[0;31mNameError\u001b[0m: name 'bench_build_avg' is not defined"
]
}
],
"source": [
"bench_avg = np.zeros_like(2, dtype=np.float32)\n",
"bench_std = np.zeros_like(2, dtype=np.float32)\n",
"#bench_recall = np.zeros_like(bench_gd, dtype=np.float32)\n",
"for i, gd in enumerate(['ivf_pq', 'nn_descent']):\n",
" index_params = cagra.IndexParams(intermediate_graph_degree=128, graph_degree=32, build_algo=\"nn_descent\", metric=metric)\n",
" build_t = %timeit -o index = cagra.build(index_params, dataset, handle=resources); resources.sync()\n",
" bench_build_avg[i] = (queries.shape[0] * build_t.loops / np.array(build_t.all_runs)).mean()\n",
" bench_build_std[i] = (queries.shape[0] * build_t.loops / np.array(build_t.all_runs)).std()\n",
" # distances, neighbors = cagra.search(search_params, index, queries, 64, handle=resources); resources.sync()\n",
" # bench_recall[i] = calc_recall(neighbors, gt_neighbors); resources.sync()\n",
"\n",
"fig, ax = plt.subplots(1, 1, figsize=plt.figaspect(1/2))\n",
"color = 'tab:green'\n",
"ax.errorbar(bench_gd, bench_build_avg, bench_build_std, color=color)\n",
"ax.set_xscale('log')\n",
"ax.set_xticks(bench_gd, bench_gd)\n",
"ax.set_xlabel('Graph degree')\n",
"ax.grid()\n",
"ax.set_ylabel('build times (s)', color=color)\n",
"\n",
"ax2 = ax.twinx()\n",
"color = 'tab:pink'\n",
"ax2.set_ylabel('Recall', color=color)\n",
"ax2.set_yticks(np.arange(0.5, 1.0, 0.05)+0.05, minor=True)\n",
"#ax2.grid(True, linestyle=\":\")\n",
"ax2.plot(bench_k, bench_recall, color=color)"
]
},
{
"cell_type": "markdown",
"id": "a0622104",
"metadata": {},
"source": [
"## Tweaking the search parameters"
]
},
{
"cell_type": "markdown",
"id": "3e3dd26e",
"metadata": {},
"source": [
"### Intermediate Top-K\n",
"Let's see how QPS depens on `itopk_size`. This is the main parameter of CAGRA search, and it controls the size of the intermediate candidates for the graph traversal held in a priority queue.\n",
"The number of neighbors `k` is fixed to 10"
]
},
{
"cell_type": "code",
"execution_count": 71,
"id": "0306ebef",
"metadata": {},
"outputs": [
{
"ename": "RuntimeError",
"evalue": "RAFT failure at file=/home/mide/raft/cpp/include/raft/neighbors/detail/cagra/search_multi_cta.cuh line=183: `num_cta_per_query` (3) * 32 must be equal to or greater than `topk` (100) when 'search_mode' is \"multi-cta\". (`num_cta_per_query`=max(`search_width`, `itopk_size`/32))\nObtained 64 stack frames\n#0 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/libraft.so(+0x1b1e34) [0x7feb4bdc5e34]\n#1 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/libraft.so(+0x21009d) [0x7feb4be2409d]\n#2 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/libraft.so(_ZN4raft9neighbors5cagra6detail16multi_cta_search6searchILj32ELj1024EfjfNS0_9filtering24none_cagra_sample_filterEE5checkEj+0x14d) [0x7feb4c5ada3d]\n#3 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/libraft.so(_ZN4raft9neighbors5cagra6searchIfjEEvRKNS_9resourcesERKNS1_13search_paramsERKNS1_5indexIT_T0_EENSt12experimental6mdspanIKSA_NSF_7extentsIlJLm18446744073709551615ELm18446744073709551615EEEENSF_12layout_rightENS_20host_device_accessorINSF_16default_accessorISH_EELNS_11memory_typeE1EEEEENSG_ISB_SJ_SK_NSL_INSM_ISB_EELSO_1EEEEENSG_IfSJ_SK_NSL_INSM_IfEELSO_1EEEEE+0x20a) [0x7feb4c5c8caa]\n#4 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/pylibraft/neighbors/cagra/cagra.cpython-310-x86_64-linux-gnu.so(+0x300d6) [0x7feb4ba450d6]\n#5 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyObject_Call+0x209) [0x558da3f11139]\n#6 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x2ec2) [0x558da3ef7cb2]\n#7 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#8 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyVectorcall_Call+0x92) [0x558da3f11322]\n#9 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/pylibraft/common/handle.cpython-310-x86_64-linux-gnu.so(+0x1ea9f) [0x7feb554d4a9f]\n#10 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/pylibraft/common/handle.cpython-310-x86_64-linux-gnu.so(+0x262b9) [0x7feb554dc2b9]\n#11 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyObject_MakeTpCall+0x26b) [0x558da3efe42b]\n#12 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x5a5e) [0x558da3efa84e]\n#13 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#14 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x4d0d) [0x558da3ef9afd]\n#15 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#16 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#17 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x14b641) [0x558da3f10641]\n#18 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyObject_Call+0xb8) [0x558da3f10fe8]\n#19 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x2ec2) [0x558da3ef7cb2]\n#20 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#21 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#22 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1d8a82) [0x558da3f9da82]\n#23 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyEval_EvalCode+0x87) [0x558da3f9d9c7]\n#24 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e0000) [0x558da3fa5000]\n#25 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x140184) [0x558da3f05184]\n#26 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x332) [0x558da3ef5122]\n#27 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#28 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#29 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#30 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#31 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#32 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1f7f4a) [0x558da3fbcf4a]\n#33 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x14a63f) [0x558da3f0f63f]\n#34 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#35 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#36 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x332) [0x558da3ef5122]\n#37 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#38 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#39 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x14b641) [0x558da3f10641]\n#40 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyObject_Call+0xb8) [0x558da3f10fe8]\n#41 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x2ec2) [0x558da3ef7cb2]\n#42 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x14b641) [0x558da3f10641]\n#43 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x13d0) [0x558da3ef61c0]\n#44 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#45 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#46 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#47 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#48 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#49 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#50 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#51 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#52 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#53 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/lib-dynload/_asyncio.cpython-310-x86_64-linux-gnu.so(+0x7d3d) [0x7fed14ba5d3d]\n#54 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x13f59b) [0x558da3f0459b]\n#55 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x2641b1) [0x558da40291b1]\n#56 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0xfbc95) [0x558da3ec0c95]\n#57 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x137d83) [0x558da3efcd83]\n#58 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x5d8c) [0x558da3efab7c]\n#59 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#60 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#61 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#62 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#63 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n",
"output_type": "error",
"traceback": [
"\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[0;31mRuntimeError\u001b[0m Traceback (most recent call last)",
"Cell \u001b[0;32mIn[71], line 10\u001b[0m\n\u001b[1;32m 7\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m i, itopk \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28menumerate\u001b[39m(bench_itopk):\n\u001b[1;32m 8\u001b[0m search_params \u001b[38;5;241m=\u001b[39m cagra\u001b[38;5;241m.\u001b[39mSearchParams(itopk_size\u001b[38;5;241m=\u001b[39mitopk)\n\u001b[0;32m---> 10\u001b[0m r \u001b[38;5;241m=\u001b[39m \u001b[43mget_ipython\u001b[49m\u001b[43m(\u001b[49m\u001b[43m)\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mrun_line_magic\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43mtimeit\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[38;5;124;43m-o cagra.search(search_params, index, queries[:n_queries], k, handle=resources); resources.sync()\u001b[39;49m\u001b[38;5;124;43m'\u001b[39;49m\u001b[43m)\u001b[49m\n\u001b[1;32m 11\u001b[0m bench_avg[i] \u001b[38;5;241m=\u001b[39m (n_queries \u001b[38;5;241m*\u001b[39m r\u001b[38;5;241m.\u001b[39mloops \u001b[38;5;241m/\u001b[39m np\u001b[38;5;241m.\u001b[39marray(r\u001b[38;5;241m.\u001b[39mall_runs))\u001b[38;5;241m.\u001b[39mmean()\n\u001b[1;32m 12\u001b[0m bench_std[i] \u001b[38;5;241m=\u001b[39m (n_queries \u001b[38;5;241m*\u001b[39m r\u001b[38;5;241m.\u001b[39mloops \u001b[38;5;241m/\u001b[39m np\u001b[38;5;241m.\u001b[39marray(r\u001b[38;5;241m.\u001b[39mall_runs))\u001b[38;5;241m.\u001b[39mstd()\n",
"File \u001b[0;32m~/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/IPython/core/interactiveshell.py:2369\u001b[0m, in \u001b[0;36mInteractiveShell.run_line_magic\u001b[0;34m(self, magic_name, line, _stack_depth)\u001b[0m\n\u001b[1;32m 2367\u001b[0m kwargs[\u001b[38;5;124m'\u001b[39m\u001b[38;5;124mlocal_ns\u001b[39m\u001b[38;5;124m'\u001b[39m] \u001b[38;5;241m=\u001b[39m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mget_local_scope(stack_depth)\n\u001b[1;32m 2368\u001b[0m \u001b[38;5;28;01mwith\u001b[39;00m \u001b[38;5;28mself\u001b[39m\u001b[38;5;241m.\u001b[39mbuiltin_trap:\n\u001b[0;32m-> 2369\u001b[0m result \u001b[38;5;241m=\u001b[39m \u001b[43mfn\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43margs\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mkwargs\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 2371\u001b[0m \u001b[38;5;66;03m# The code below prevents the output from being displayed\u001b[39;00m\n\u001b[1;32m 2372\u001b[0m \u001b[38;5;66;03m# when using magics with decodator @output_can_be_silenced\u001b[39;00m\n\u001b[1;32m 2373\u001b[0m \u001b[38;5;66;03m# when the last Python token in the expression is a ';'.\u001b[39;00m\n\u001b[1;32m 2374\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28mgetattr\u001b[39m(fn, magic\u001b[38;5;241m.\u001b[39mMAGIC_OUTPUT_CAN_BE_SILENCED, \u001b[38;5;28;01mFalse\u001b[39;00m):\n",
"File \u001b[0;32m~/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/IPython/core/magics/execution.py:1164\u001b[0m, in \u001b[0;36mExecutionMagics.timeit\u001b[0;34m(self, line, cell, local_ns)\u001b[0m\n\u001b[1;32m 1162\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m index \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(\u001b[38;5;241m0\u001b[39m, \u001b[38;5;241m10\u001b[39m):\n\u001b[1;32m 1163\u001b[0m number \u001b[38;5;241m=\u001b[39m \u001b[38;5;241m10\u001b[39m \u001b[38;5;241m*\u001b[39m\u001b[38;5;241m*\u001b[39m index\n\u001b[0;32m-> 1164\u001b[0m time_number \u001b[38;5;241m=\u001b[39m \u001b[43mtimer\u001b[49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mtimeit\u001b[49m\u001b[43m(\u001b[49m\u001b[43mnumber\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 1165\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m time_number \u001b[38;5;241m>\u001b[39m\u001b[38;5;241m=\u001b[39m \u001b[38;5;241m0.2\u001b[39m:\n\u001b[1;32m 1166\u001b[0m \u001b[38;5;28;01mbreak\u001b[39;00m\n",
"File \u001b[0;32m~/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/IPython/core/magics/execution.py:158\u001b[0m, in \u001b[0;36mTimer.timeit\u001b[0;34m(self, number)\u001b[0m\n\u001b[1;32m 156\u001b[0m gc\u001b[38;5;241m.\u001b[39mdisable()\n\u001b[1;32m 157\u001b[0m \u001b[38;5;28;01mtry\u001b[39;00m:\n\u001b[0;32m--> 158\u001b[0m timing \u001b[38;5;241m=\u001b[39m \u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43minner\u001b[49m\u001b[43m(\u001b[49m\u001b[43mit\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;28;43mself\u001b[39;49m\u001b[38;5;241;43m.\u001b[39;49m\u001b[43mtimer\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 159\u001b[0m \u001b[38;5;28;01mfinally\u001b[39;00m:\n\u001b[1;32m 160\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m gcold:\n",
"File \u001b[0;32m<magic-timeit>:1\u001b[0m, in \u001b[0;36minner\u001b[0;34m(_it, _timer)\u001b[0m\n",
"File \u001b[0;32mhandle.pyx:225\u001b[0m, in \u001b[0;36mpylibraft.common.handle.auto_sync_handle.wrapper\u001b[0;34m()\u001b[0m\n",
"File \u001b[0;32m~/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/pylibraft/common/outputs.py:83\u001b[0m, in \u001b[0;36mauto_convert_output.<locals>.wrapper\u001b[0;34m(*args, **kwargs)\u001b[0m\n\u001b[1;32m 81\u001b[0m \u001b[38;5;129m@functools\u001b[39m\u001b[38;5;241m.\u001b[39mwraps(f)\n\u001b[1;32m 82\u001b[0m \u001b[38;5;28;01mdef\u001b[39;00m \u001b[38;5;21mwrapper\u001b[39m(\u001b[38;5;241m*\u001b[39margs, \u001b[38;5;241m*\u001b[39m\u001b[38;5;241m*\u001b[39mkwargs):\n\u001b[0;32m---> 83\u001b[0m ret_value \u001b[38;5;241m=\u001b[39m \u001b[43mf\u001b[49m\u001b[43m(\u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43margs\u001b[49m\u001b[43m,\u001b[49m\u001b[43m \u001b[49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[38;5;241;43m*\u001b[39;49m\u001b[43mkwargs\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m 84\u001b[0m \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28misinstance\u001b[39m(ret_value, pylibraft\u001b[38;5;241m.\u001b[39mcommon\u001b[38;5;241m.\u001b[39mdevice_ndarray):\n\u001b[1;32m 85\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m convert_to_cai_type(ret_value)\n",
"File \u001b[0;32mcagra.pyx:746\u001b[0m, in \u001b[0;36mpylibraft.neighbors.cagra.cagra.search\u001b[0;34m()\u001b[0m\n",
"File \u001b[0;32mcagra.pyx:747\u001b[0m, in \u001b[0;36mpylibraft.neighbors.cagra.cagra.search\u001b[0;34m()\u001b[0m\n",
"\u001b[0;31mRuntimeError\u001b[0m: RAFT failure at file=/home/mide/raft/cpp/include/raft/neighbors/detail/cagra/search_multi_cta.cuh line=183: `num_cta_per_query` (3) * 32 must be equal to or greater than `topk` (100) when 'search_mode' is \"multi-cta\". (`num_cta_per_query`=max(`search_width`, `itopk_size`/32))\nObtained 64 stack frames\n#0 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/libraft.so(+0x1b1e34) [0x7feb4bdc5e34]\n#1 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/libraft.so(+0x21009d) [0x7feb4be2409d]\n#2 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/libraft.so(_ZN4raft9neighbors5cagra6detail16multi_cta_search6searchILj32ELj1024EfjfNS0_9filtering24none_cagra_sample_filterEE5checkEj+0x14d) [0x7feb4c5ada3d]\n#3 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/libraft.so(_ZN4raft9neighbors5cagra6searchIfjEEvRKNS_9resourcesERKNS1_13search_paramsERKNS1_5indexIT_T0_EENSt12experimental6mdspanIKSA_NSF_7extentsIlJLm18446744073709551615ELm18446744073709551615EEEENSF_12layout_rightENS_20host_device_accessorINSF_16default_accessorISH_EELNS_11memory_typeE1EEEEENSG_ISB_SJ_SK_NSL_INSM_ISB_EELSO_1EEEEENSG_IfSJ_SK_NSL_INSM_IfEELSO_1EEEEE+0x20a) [0x7feb4c5c8caa]\n#4 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/pylibraft/neighbors/cagra/cagra.cpython-310-x86_64-linux-gnu.so(+0x300d6) [0x7feb4ba450d6]\n#5 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyObject_Call+0x209) [0x558da3f11139]\n#6 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x2ec2) [0x558da3ef7cb2]\n#7 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#8 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyVectorcall_Call+0x92) [0x558da3f11322]\n#9 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/pylibraft/common/handle.cpython-310-x86_64-linux-gnu.so(+0x1ea9f) [0x7feb554d4a9f]\n#10 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/site-packages/pylibraft/common/handle.cpython-310-x86_64-linux-gnu.so(+0x262b9) [0x7feb554dc2b9]\n#11 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyObject_MakeTpCall+0x26b) [0x558da3efe42b]\n#12 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x5a5e) [0x558da3efa84e]\n#13 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#14 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x4d0d) [0x558da3ef9afd]\n#15 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#16 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#17 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x14b641) [0x558da3f10641]\n#18 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyObject_Call+0xb8) [0x558da3f10fe8]\n#19 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x2ec2) [0x558da3ef7cb2]\n#20 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#21 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#22 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1d8a82) [0x558da3f9da82]\n#23 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyEval_EvalCode+0x87) [0x558da3f9d9c7]\n#24 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e0000) [0x558da3fa5000]\n#25 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x140184) [0x558da3f05184]\n#26 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x332) [0x558da3ef5122]\n#27 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#28 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#29 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#30 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#31 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#32 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1f7f4a) [0x558da3fbcf4a]\n#33 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x14a63f) [0x558da3f0f63f]\n#34 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#35 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#36 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x332) [0x558da3ef5122]\n#37 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#38 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#39 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x14b641) [0x558da3f10641]\n#40 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(PyObject_Call+0xb8) [0x558da3f10fe8]\n#41 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x2ec2) [0x558da3ef7cb2]\n#42 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x14b641) [0x558da3f10641]\n#43 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x13d0) [0x558da3ef61c0]\n#44 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#45 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#46 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#47 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#48 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#49 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#50 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#51 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x1bb0) [0x558da3ef69a0]\n#52 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x1e273d) [0x558da3fa773d]\n#53 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/lib/python3.10/lib-dynload/_asyncio.cpython-310-x86_64-linux-gnu.so(+0x7d3d) [0x7fed14ba5d3d]\n#54 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x13f59b) [0x558da3f0459b]\n#55 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x2641b1) [0x558da40291b1]\n#56 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0xfbc95) [0x558da3ec0c95]\n#57 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(+0x137d83) [0x558da3efcd83]\n#58 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x5d8c) [0x558da3efab7c]\n#59 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#60 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#61 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n#62 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyEval_EvalFrameDefault+0x735) [0x558da3ef5525]\n#63 in /home/mide/miniconda3/envs/all_cuda-118_arch-x86_64/bin/python(_PyFunction_Vectorcall+0x6f) [0x558da3f04f8f]\n"
]
}
],
"source": [
"n_queries = 10\n",
"k = 100\n",
"bench_itopk = (np.arange(100, 500, 50)).astype(np.int32)\n",
"bench_avg = np.zeros_like(bench_itopk, dtype=np.float32)\n",
"bench_std = np.zeros_like(bench_itopk, dtype=np.float32)\n",
"bench_recall = np.zeros_like(bench_itopk, dtype=np.float32)\n",
"for i, itopk in enumerate(bench_itopk):\n",
" search_params = cagra.SearchParams(itopk_size=itopk)\n",
" \n",
" r = %timeit -o cagra.search(search_params, index, queries[:n_queries], k, handle=resources); resources.sync()\n",
" bench_avg[i] = (n_queries * r.loops / np.array(r.all_runs)).mean()\n",
" bench_std[i] = (n_queries * r.loops / np.array(r.all_runs)).std()\n",
" distances, neighbors = cagra.search(search_params, index, queries[:n_queries], k, handle=resources); resources.sync()\n",
" bench_recall[i] = calc_recall(neighbors, gt_neighbors[:n_queries]); resources.sync()\n",
"\n",
"fig, ax = plt.subplots(1, 1, figsize=plt.figaspect(1/2))\n",
"color = 'tab:green'\n",
"ax.errorbar(bench_itopk, bench_avg, bench_std, color=color)\n",
"#ax.set_xscale('log')\n",
"ax.set_xticks(bench_itopk, bench_itopk)\n",
"ax.set_xlabel('itopk')\n",
"ax.grid()\n",
"ax.set_ylabel('QPS', color=color)\n",
"#ax.set_yscale('log')\n",
"\n",
"ax2 = ax.twinx()\n",
"color = 'tab:pink'\n",
"ax2.set_ylabel('Recall', color=color)\n",
"ax2.set_yticks(np.arange(0.5, 1.0, 0.05)+0.05, minor=True)\n",
"#ax2.grid(True, linestyle=\":\")\n",
"ax2.plot(bench_itopk, bench_recall, color=color)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "6a160779",
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3 (ipykernel)",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.10.13"
}
},
"nbformat": 4,
"nbformat_minor": 5
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment