Cain

Convolutional-Filter Code-Generator for Cellular-Processor-Arrays

Installation

1. git clone https://github.com/ed741/cain.git
2. cd cain
3. mvn install

Installing using Maven will run tests and so should confirm that Cain is working.

Using Cain

Cain uses a JSON input format to define the filter and search parameters to use. Examples can be found in ./examples.

To run an example use:

java -jar target/cain-3.1.jar examples/sobel.json

JSON Format

The primary way to produce code is to specify a search using JSON. It is of course possible to use Cain like a library and configure it how you like but for non-automated, or trivially automated use the Json format is likely to be most helpful. Tables like the one below show what JSON tags can be specified, and if there is no default then they must be specified. Where the valid value is itself an object that has multiple implementation options we use the "name" tag to specify the implementation.

This is the sobel example

{"name":"Sobel",
  "target": "scamp5",
  "mode": "analogue",
  "goalSystem":"atom",
  
  "runConfig":{
    "searchTime":1000,
    "timeOut":true,
    "workers":4,
    "traversalAlgorithm":"CGDS",
    "costFunction":"CircuitDepthThenLength",
    "liveCounter":true,
    "livePrintPlans":2,
    "quiet": false,
    "initialMaxDepth":200,
    "forcedDepthReduction":1,
    "initialMaxCost":2147483647,
    "forcedCostReduction":0,
    "allowableAtomsCoefficient":2,
    "goalReductionsPerStep":1,
    "goalReductionsTolerance":1
  },

  "maxApproximationDepth":3,
  "maxApproximationError":0,
  "filter":{
    "A": {"depth":0,
      "array":
      [ [1, 0, -1],
        [2, 0, -2],
        [1, 0, -1]
      ]}
  },

  "registerAllocator": {
    "name": "linearScan",
    "availableRegisters":["A","B","C","D","E","F"],
    "initialRegisters":["A"]
  },

  "pairGen":{
    "strategy": {
      "name":"Threshold",
      "threshold":10,
      "heuristic": {"name":"Pattern"},
      "ops": "all",
      "above": {
        "name":"AtomDistance"
      }
    },
    "outputFormat": {
      "name": "defaultFormat"
    }
  },

  "verifier":"Scamp5Emulator"

}

| token id | valid value | Default | Description | | ----------------- |:-------------:|:-------:| ------------ | | id | Any String | | The arbitary name of this search configuration. | | verbose | Integer | 10 | This value controls the verbosity of the setup and checking of the search, not the search itself (see 'runConfig' for search verbosity rules) less than 0 means no output, 0 means critical only, and so on, more than 10 will print debug information. | | target | | | This determines the target architecture as well as fundamental things such as implementation of the Goals Cain will search for | | . | "scamp5" | | target the scamp5 system, see below | | runConfig | RunConfig (see below) | | The run configutation for Cain, including parameters for search time, traversal algorithm, and cost function. |

RunConfig

The RunConfig defines the behaviour of the Reverse Search Algorithm, but not any of the Pair Generation or Huristics.

| token id | valid value | Description | | ------------- |:-------------:| ------------ | | searchTime | Integer | The timeout for searching| | timeOut | Boolean | Whether or not Cain should timeout when searching. If Cain is set to use more than 1 worker it will never stop by itself, even if all nodes have been explored | | workers | Integer | The number for worker threads to use (worker threads search semi-independently using different instances of the same traversal algorithm). This does not effect multi-threading performed within the pairGeneration invocation of a worker thread | | traversalAlgorithm | | The traversal Algorithm to use. CGDS is recommended. | | . | "CGDS" | Child-Generator-Deque-Search - The recommended algorithm | | . | "BFS" | Breadth-First-Search | | . | "DFS" | Depth-First-Search | | . | "HOS" | Heir-Ordered-Search (a priority queue of children are stored such that all 1st children are visited before 2nd children, 2nd before 3rd, and so on | . | "BestFirstSearch"| The Heuristic used in the BestFirstSearch is the "costFunction" || | costFunction | | The cost function to use to compare plans, used to decide if a state has been seen before in a shorter plan, and used to determine the best plan found.| | . | "CircuitDepth"| The Maximum circuit depth by 'search steps' regardless of the cost of particular instructions | | . | "InstructionCost"| The total cost of every instruction in the plan so far | | . | "CircuitDepthThenLength" | First order by the "CircuitDepth" metric then "PlanLength" | | . | "LengthThenCircuitDepth" | First order by the "PlanLength" metric then "CircuitDepth" | | . | "PlanLength" | Order by the number of 'search steps' in the plan aka the search depth reguardless of the cost of particular instructions | | liveCounter | Boolean | If a live indication of search progress should be printed during the search. | | livePrintPlans | Integer | If >0 then finding a new plan is announced as the search finds it. If > 1 then that plan's steps are also printed. | | quiet | Boolean | when set to false Cain will not announce the search starting and stopping or print search statistics. | | initialMaxDepth | Integer | The initial maximum number of instruction allowed in a plan before giving up on finding a valid plan. | | forcedDepthReduction| Integer | When a new valid plan is found the MaxDepth is set to the length of that plan minus this value. | | initialMaxCost | Integer | The initial MaxCost, the highest cost a plan is allowed. more costly plans are not searched. | | forcedCostReduction | Integer | When a new valid plan is found the MaxCost is set to the cost of that plan minus this value. | | allowableAtomsCoefficient | Integer | States with more atoms than the filter we are generating multiplied by this value, plus the atoms in the inital Goals are rejected and not searched | | goalReductionsPerStep | Integer | The number of goals that can be removed from the State in one transformation. This allows Cain to prune States with more exess goals in the goal-bag than instructions left before MaxDepth. | | goalReductionsTolerance | Integer | This value is added to the calculation for pruning by "goalReductionsPerStep" to allow for a lower "goalReductionsPerStep" if only a few instructions might reduce the number of goals by more than "goalReductionsPerStep". |

target:"scamp5"

If target is "scamp5" then the "mode" tag must be present:

| token id | valid value | Default | Description | | ---------- |:-------------:|:-------:| ------------ | | mode | | | Specifies the paradigms and features to use, to produce code for the scamp5 device | | . | "analogue" | | Use the scamp5's analogue functionality to compute a convolutional filter | | . | "digital" | | Use the scamp5's digital functionality to compute a convolutional filter (doesn't support negative numbers) | | . | "superpixel" | | Use the scamp5's digital functionality, where multiple Processing element form a single 'super pixel' to compute a convolutional filter | | registerAllocator | RegisterAllocator (see below) | | The registerAllocator to use. | filter | Filter (see below) | | The mapping from Registers to the kernels to be compiled. | | maxApproximationDepth | Integer | | The maximum number of divisions by 2 that we allow when approximating the filter for binary encoding. Aka the resolution of the approximation, a value of 5 would mean the filter weights are approximate no closer than to the closest 1/32nd. | | maxApproximationError | Double | | The allowable cumulative error of the approximation of a filter. A lower error means higher accuracy of results but if the weights are not simple fractions with binary number denominators then program length will increase significantly. | | pairGen | PairGen (see below) | | The pair generation configuration, including any configuration parameters to give the Generator to specify things like bit-layout. | | verifier | | | The verifier to use to ensure the produced code is correct. | | . | "none" | | Do no verification. | | . | "Scamp5Emulator" | | Verify using a Scamp5 Emulator, only avalable if mode is "analogue" |

mode:

If mode is "analogue" or "digital" then must also select a goalSystem:

| token id | valid value | Default | Description | | ---------- |:-------------:|:-------:| ------------ | | goalSystem | | | Specifies the implementation used to store 'Goals' representing the convolutional kernels | | . | "atom" | | This uses a list of atoms to represent a kernel, based on Debrunner's AUKE (code) | | . | "array" | | This uses an array of weights instead, providing the same functionality with better performance, and is recommend |

When mode is "superpixel" an adapted implementation of the "array" implementation is always used.

RegisterAllocator

The Register allocator defines the registers Cain can use as well as the algorithm to allocate them, but there is some nuance to them depending on the mode selected.

• If the mode is "analogue" then registers, specified as strings are directly the outp