evaluation/EXP-10-dining-philosophers-processes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# Protocol: Comparison of Exploration of the Dining Philosophers Problem with Different Number of Processes\n",
    "\n",
    "Date: 17.09.2021\n",
    "\n",
    "## Question\n",
    "\n",
    "Does the number of processes, and by that the state space size, affect the state space exploration performance on the Dining Philosophers Problem?\n",
    "\n",
    "## Hypothesis\n",
    "\n",
    "The paper suggests that when the state space size of a model surpasses the hash table capacity, state space exploration slows down significantly, resulting in a much higher number of VTs needed to explore >99% of the state space.\n",
    "\n",
    "Thus, we expect the exploration to slow down starting with Phils-12 on a $2^{18}$ hash table.\n",
    "\n",
    "## Setup\n",
    "\n",
    "- GPU: NVIDIA GeForce RTX 2080 Ti\n",
    "- Program: `main` branch, commit e160572\n",
    "- Model: Philosophers model\n",
    "- CUDA_FLAGS: `-DGRAPPLE_MODEL=PhilosophersStateV2`\n",
    "\n",
    "## Implementation\n",
    "\n",
    "To control the number of processes, we have to alter the constants `kProcesses` and `kStateSpaceSize` in `src/models/PhilosophersStateV2.cuh`.\n",
    "\n",
    "First, we set `kProcesses = 11` and `kStateSpaceSize = 177146`.\n",
    "\n",
    "We stop the experiment after 10 runs as exhaustive state space coverage is already achieved after the first run.\n",
    "\n",
    "```\n",
    "$ time ./build/grapple -s 1736331306 -n 10 -q\n",
    "run,block,thread,state,uniques,visited,visited_percent,vts,total_visited\n",
    "0,,,,,178913,100.998,250,31481577\n",
    "1,,,,,178913,100.998,500,31480442\n",
    "2,,,,,178913,100.998,750,31480607\n",
    "...\n",
    "\n",
    "real    0m4.468s\n",
    "user    0m4.230s\n",
    "sys     0m0.176s\n",
    "```\n",
    "\n",
    "Full output data is available at [EXP-10-dining-philosophers-processes-1.csv](./data/EXP-10-dining-philosophers-processes-1.csv).\n",
    "\n",
    "---\n",
    "\n",
    "Then, we set `kProcesses = 12` and `kStateSpaceSize = 531440`.\n",
    "\n",
    "```\n",
    "$ time ./build/grapple -s 1736331306 -n 100 -q\n",
    "run,block,thread,state,uniques,visited,visited_percent,vts,total_visited\n",
    "0,,,,,536054,100.868,250,51628961\n",
    "1,,,,,536585,100.968,500,51627548\n",
    "2,,,,,536585,100.968,750,51624312\n",
    "...\n",
    "\n",
    "real    1m7.006s\n",
    "user    1m6.729s\n",
    "sys     0m0.212s\n",
    "```\n",
    "\n",
    "Full output data is available at [EXP-10-dining-philosophers-processes-2.csv](./data/EXP-10-dining-philosophers-processes-2.csv).\n",
    "\n",
    "---\n",
    "\n",
    "For the last experiment, we set `kProcesses = 13` and `kStateSpaceSize = 1594322`.\n",
    "\n",
    "```\n",
    "$ time ./build/grapple -s 1736331306 -n 300 -q\n",
    "\n",
    "real    3m41.322s\n",
    "user    3m40.929s\n",
    "sys     0m0.276s\n",
    "```\n",
    "\n",
    "Full output data is available at [EXP-10-dining-philosophers-processes-3.csv](./data/EXP-10-dining-philosophers-processes-3.csv).\n",
    "\n",
    "## Evaluation\n",
    "\n",
    "| Model | Hash Table Utilization | # of VTs to explore |\n",
    "|-------|------------------------|---------------------|\n",
    "| DP-11 | ~68% | 100% in 250 |\n",
    "| DP-12 | ~203% | 100% in 250 |\n",
    "| DP-13 | ~608% | 100% in 53250 |\n",
    "\n",
    "## Conclusion, Discussion\n",
    "\n",
    "The state space size of DP-13 is 9x the state space size of DP-11. However, exploring about 100% of DP-13's state space takes 213x as many VTs as for DP-11.\n",
    "\n",
    "Thus, our hypothesis is confirmed on the dining philosophers model."
   ],
   "metadata": {}
  }
 ],
 "metadata": {
  "orig_nbformat": 4,
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}