<p align="center">
<a title="tdene.github.io/synth_opt_adders" href="https://tdene.github.io/synth_opt_adders"><img src="https://img.shields.io/website?longCache=true&style=flat-square&label=tdene.github.io%2Fsynth_opt_adders&logo=GitHub&logoColor=fff&up_color=blueviolet&up_message=Read%20now%20%E2%9E%9A&url=https%3A%2F%2Ftdene.github.io%2Fsynth_opt_adders%2Findex.html"></a><!--
-->
<a title="Apache-2.0" href="https://github.com/tdene/synth_opt_adders/blob/main/LICENSE"><img src="https://img.shields.io/github/license/tdene/synth_opt_adders?longCache=true&style=flat-square&logo=Apache&label=Code"></a><!--
-->
<a title="'unit_tests' workflow Status"
href="https://github.com/tdene/synth_opt_adders/actions?query=workflow%3Aunit_tests"
><img alt="'unit_tests' workflow Status" src="https://img.shields.io/github/workflow/status/tdene/synth_opt_adders/Python%20package/main?longCache=true&style=flat-square&label=unit_tests&logo=GitHub%20Actions&logoColor=fff"
/></a><!--
-->
<a title="'docs workflow Status"
href="https://github.com/tdene/synth_opt_adders/actions?query=workflow%3Adocs"
><img alt="'docs workflow Status" src="https://img.shields.io/github/workflow/status/tdene/synth_opt_adders/docs/main?longCache=true&style=flat-square&label=docs&logo=GitHub%20Actions&logoColor=fff"
/></a>
</p>
[](https://colab.research.google.com/github/tdene/synth_opt_adders/blob/master/docs/notebooks/intro.ipynb)
# Quick-start guide
For detailed documentation, please click the "Read now" button above.
To install this tool:
```python
pip install --upgrade pptrees
```
To generate a test adder:
```python
from pptrees.AdderForest import AdderForest as forest
width = 9
f = forest(width, alias = "sklansky")
f.hdl('adder.v')
f.gif('adder.gif')
```
# Hardware synthesis of arithmetic operations
Arithmetic operations are important. Addition, in particular, is ubiquitous. When a RISC-V processor boots into Linux, for example, roughly 70% of the assembly instructions use addition.
Circuit design involves trade-offs, typically phrased in terms of power vs performance (speed) vs area.<br>
These trade-offs certainly apply to arithmetic operations. Circuits can be very fast and power-hungry, very slow and power-efficient, or anywhere in between.
Moreso, these trade-offs occur on a bit-by-bit basis. If a circuit generates a 64-bit result, each bit of the result can be optimized for power, speed, or area.<br>
Often this becomes essential, as some bits must be processed faster than others.
These trade-offs create a Pareto front of possible circuits, each optimal for a specific situation.<br>
The implementation of such arithmetic circuits is non-trivial, as is the design space, for reasons elaborated upon in the main documentation.
## Traditional framework
How can these circuits be generated and explored, especially when it comes to arithmetic operations?<br>
Historically, one particular method for hardware addition has been used and researched since the 1980s.<br>
This method conceptualizes circuits using the type of diagram shown below, and is implemented by version v0.4.5 of this library.
The diagram above displays a binary expression graph that performs the desired computation.<br>
The lines in the diagram are edges in the graph, carrying data from the top to the bottom. Each ■ represents a node that performs a simple computation.
This type of diagram, and of implementation, can best be described as an **n**-rooted binary tree that is drawn upside-down.<br>
There are many ways to design such circuits, and the design space can be explored as seen below.
Such an exploration is performed by identifying the following three simple patterns throughout the graph, and performing point-targeted transforms.
<img src="https://github.com/tdene/synth_opt_adders/blob/main/docs/diagrams/L.png?raw=true" width="150"/>
<img src="https://github.com/tdene/synth_opt_adders/blob/main/docs/diagrams/T.png?raw=true" width="150"/>
<img src="https://github.com/tdene/synth_opt_adders/blob/main/docs/diagrams/F.png?raw=true" width="150"/>
This method is computationally expensive, requiring exponential run-time.
Moreover, any such exploration using classic diagrams and conceptualization is incomplete and overly complicated.<br>
It is unclear how large the design space, and it is impossible to represent all valid designs.<br>
Under this framework, simple structures become obfuscated, while more advanced optimizations become impossible to implement or theoretically describe.
Arithmetic computation architectures are not **n**-rooted binary trees.
## Revised framework
Instead, this library chooses to express arithmetic computation in terms of forests of **n** trees.
This approach results directly from the underlying mathematics, allowing circuit designers to leverage decades of research in graph theory and toplogy.
```python
from pptrees.AdderForest import AdderForest as forest
width = 17
f = forest(width, alias = "sklansky")
f
```
The diagram above displays the same circuit as the one from the previous section.
Each frame of the animation computes an individual bit of the final sum.
It is immediately clear how large the design space is:
```python
from pptrees.util import catalan
width = 17
number_of_designs = 1
for a in range(width):
number_of_designs = number_of_designs * catalan(a)
print(number_of_designs)
```
323828772071827218688291208408423952910530531102720000000
It is straightforward to generate any valid tree in O(n lg(n)) time:
```python
from pptrees.AdderForest import AdderForest as forest
from pptrees.util import catalan_bounds
width = 17
print("The maximum tree sizes for a forest of width {0} are {1}".format(width,catalan_bounds(width)))
f = forest(width, tree_start_points = [0, 0, 0, 2, 5, 37, 74, 214, 214, 670, 2000, 5463, 12351, 135151, 461614, 1512512, 8351854, 3541563])
f
```
The maximum tree sizes for a forest of width 17 are [0, 0, 1, 4, 13, 41, 131, 428, 1429, 4861, 16795, 58785, 208011, 742899, 2674439, 9694844, 35357669]
Similarly, it is straightforward to label any valid tree in O(n lg(n)) time:
```python
from pptrees.AdderForest import AdderForest as forest
f = forest(width, tree_start_points = [0, 0, 0, 2, 5, 37, 74, 214, 214, 670, 2000, 5463, 12351, 135151, 461614, 1512512, 8351854, 3541563])
for t in enumerate(f.trees):
print("The rank of tree {0} in this forest is {1}".format(t[0],t[1].rank()))
```
The rank of tree 0 in this forest is 0
The rank of tree 1 in this forest is 0
The rank of tree 2 in this forest is 0
The rank of tree 3 in this forest is 2
The rank of tree 4 in this forest is 5
The rank of tree 5 in this forest is 37
The rank of tree 6 in this forest is 74
The rank of tree 7 in this forest is 214
The rank of tree 8 in this forest is 214
The rank of tree 9 in this forest is 670
The rank of tree 10 in this forest is 2000
The rank of tree 11 in this forest is 5463
The rank of tree 12 in this forest is 12351
The rank of tree 13 in this forest is 135151
The rank of tree 14 in this forest is 461614
The rank of tree 15 in this forest is 1512512
The rank of tree 16 in this forest is 8351854
Factorization optimizations such that of Ling, a concept that cannot be described by the old framework, are a straightforward decomposition of the "gp" pre-processing nodes into "g" and "p", followed by a stereoscopic combination of two such tree halves.
Sparseness, another concept that is difficult to understand under the old framework, arises naturally.
Nested sparseness, a novel concept that can reduce the circuits' logical depth, has not been discovered by prior literature due to its incompatibility with the traditional framework.
```python
from pptrees.AdderTree import AdderTree as tree
width = 8
t = tree(width, start_point = 214)
t
```
This framework allows for a full and efficient exploration of the entire design space.
In addition, these concepts don't just apply to binary addition. They apply to a wide range of hardware operations.
Raw data
{
"_id": null,
"home_page": "https://github.com/tdene/synth_opt_adders",
"name": "pptrees",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.6.*",
"maintainer_email": "",
"keywords": "hardware adders prefix",
"author": "tdene",
"author_email": "teodord.ene@gmail.com",
"download_url": "https://files.pythonhosted.org/packages/89/e5/c71160f13eb762c7d1b38937ed67e385fb7f1e05ac9828b5a8dd94ce1de5/pptrees-1.3.3.tar.gz",
"platform": null,
"description": "<p align=\"center\">\n <a title=\"tdene.github.io/synth_opt_adders\" href=\"https://tdene.github.io/synth_opt_adders\"><img src=\"https://img.shields.io/website?longCache=true&style=flat-square&label=tdene.github.io%2Fsynth_opt_adders&logo=GitHub&logoColor=fff&up_color=blueviolet&up_message=Read%20now%20%E2%9E%9A&url=https%3A%2F%2Ftdene.github.io%2Fsynth_opt_adders%2Findex.html\"></a><!--\n -->\n <a title=\"Apache-2.0\" href=\"https://github.com/tdene/synth_opt_adders/blob/main/LICENSE\"><img src=\"https://img.shields.io/github/license/tdene/synth_opt_adders?longCache=true&style=flat-square&logo=Apache&label=Code\"></a><!--\n -->\n <a title=\"'unit_tests' workflow Status\"\n href=\"https://github.com/tdene/synth_opt_adders/actions?query=workflow%3Aunit_tests\"\n ><img alt=\"'unit_tests' workflow Status\" src=\"https://img.shields.io/github/workflow/status/tdene/synth_opt_adders/Python%20package/main?longCache=true&style=flat-square&label=unit_tests&logo=GitHub%20Actions&logoColor=fff\"\n /></a><!--\n -->\n <a title=\"'docs workflow Status\"\n href=\"https://github.com/tdene/synth_opt_adders/actions?query=workflow%3Adocs\"\n ><img alt=\"'docs workflow Status\" src=\"https://img.shields.io/github/workflow/status/tdene/synth_opt_adders/docs/main?longCache=true&style=flat-square&label=docs&logo=GitHub%20Actions&logoColor=fff\"\n /></a>\n</p>\n\n[](https://colab.research.google.com/github/tdene/synth_opt_adders/blob/master/docs/notebooks/intro.ipynb)\n\n# Quick-start guide\n\nFor detailed documentation, please click the \"Read now\" button above.\n\nTo install this tool:\n\n\n```python\npip install --upgrade pptrees\n```\n\nTo generate a test adder:\n\n\n```python\nfrom pptrees.AdderForest import AdderForest as forest\n\nwidth = 9\nf = forest(width, alias = \"sklansky\")\nf.hdl('adder.v')\nf.gif('adder.gif')\n```\n\n# Hardware synthesis of arithmetic operations\n\nArithmetic operations are important. Addition, in particular, is ubiquitous. When a RISC-V processor boots into Linux, for example, roughly 70% of the assembly instructions use addition.\n\nCircuit design involves trade-offs, typically phrased in terms of power vs performance (speed) vs area.<br>\nThese trade-offs certainly apply to arithmetic operations. Circuits can be very fast and power-hungry, very slow and power-efficient, or anywhere in between.\n\nMoreso, these trade-offs occur on a bit-by-bit basis. If a circuit generates a 64-bit result, each bit of the result can be optimized for power, speed, or area.<br>\nOften this becomes essential, as some bits must be processed faster than others.\n\nThese trade-offs create a Pareto front of possible circuits, each optimal for a specific situation.<br>\nThe implementation of such arithmetic circuits is non-trivial, as is the design space, for reasons elaborated upon in the main documentation.\n\n## Traditional framework\n\nHow can these circuits be generated and explored, especially when it comes to arithmetic operations?<br>\nHistorically, one particular method for hardware addition has been used and researched since the 1980s.<br>\nThis method conceptualizes circuits using the type of diagram shown below, and is implemented by version v0.4.5 of this library.\n\n\n\nThe diagram above displays a binary expression graph that performs the desired computation.<br>\nThe lines in the diagram are edges in the graph, carrying data from the top to the bottom. Each \u25a0 represents a node that performs a simple computation.\n\nThis type of diagram, and of implementation, can best be described as an **n**-rooted binary tree that is drawn upside-down.<br>\nThere are many ways to design such circuits, and the design space can be explored as seen below.\n\n\n\nSuch an exploration is performed by identifying the following three simple patterns throughout the graph, and performing point-targeted transforms.\n\n<img src=\"https://github.com/tdene/synth_opt_adders/blob/main/docs/diagrams/L.png?raw=true\" width=\"150\"/>\n\n<img src=\"https://github.com/tdene/synth_opt_adders/blob/main/docs/diagrams/T.png?raw=true\" width=\"150\"/>\n\n<img src=\"https://github.com/tdene/synth_opt_adders/blob/main/docs/diagrams/F.png?raw=true\" width=\"150\"/>\n\nThis method is computationally expensive, requiring exponential run-time.\n\nMoreover, any such exploration using classic diagrams and conceptualization is incomplete and overly complicated.<br>\nIt is unclear how large the design space, and it is impossible to represent all valid designs.<br>\nUnder this framework, simple structures become obfuscated, while more advanced optimizations become impossible to implement or theoretically describe.\n\nArithmetic computation architectures are not **n**-rooted binary trees.\n\n## Revised framework\n\nInstead, this library chooses to express arithmetic computation in terms of forests of **n** trees.\n\nThis approach results directly from the underlying mathematics, allowing circuit designers to leverage decades of research in graph theory and toplogy.\n\n\n```python\nfrom pptrees.AdderForest import AdderForest as forest\n\nwidth = 17\nf = forest(width, alias = \"sklansky\")\nf\n```\n\n\n\n\n\n\n\n\n\n\nThe diagram above displays the same circuit as the one from the previous section.\n\nEach frame of the animation computes an individual bit of the final sum.\n\nIt is immediately clear how large the design space is:\n\n\n```python\nfrom pptrees.util import catalan\n\nwidth = 17\nnumber_of_designs = 1\nfor a in range(width):\n number_of_designs = number_of_designs * catalan(a)\nprint(number_of_designs)\n```\n\n 323828772071827218688291208408423952910530531102720000000\n\n\nIt is straightforward to generate any valid tree in O(n lg(n)) time:\n\n\n```python\nfrom pptrees.AdderForest import AdderForest as forest\nfrom pptrees.util import catalan_bounds\n\nwidth = 17\nprint(\"The maximum tree sizes for a forest of width {0} are {1}\".format(width,catalan_bounds(width)))\nf = forest(width, tree_start_points = [0, 0, 0, 2, 5, 37, 74, 214, 214, 670, 2000, 5463, 12351, 135151, 461614, 1512512, 8351854, 3541563])\nf\n```\n\n The maximum tree sizes for a forest of width 17 are [0, 0, 1, 4, 13, 41, 131, 428, 1429, 4861, 16795, 58785, 208011, 742899, 2674439, 9694844, 35357669]\n\n\n\n\n\n\n\n\n\n\n\nSimilarly, it is straightforward to label any valid tree in O(n lg(n)) time:\n\n\n```python\nfrom pptrees.AdderForest import AdderForest as forest\n\nf = forest(width, tree_start_points = [0, 0, 0, 2, 5, 37, 74, 214, 214, 670, 2000, 5463, 12351, 135151, 461614, 1512512, 8351854, 3541563])\nfor t in enumerate(f.trees):\n print(\"The rank of tree {0} in this forest is {1}\".format(t[0],t[1].rank()))\n```\n\n The rank of tree 0 in this forest is 0\n The rank of tree 1 in this forest is 0\n The rank of tree 2 in this forest is 0\n The rank of tree 3 in this forest is 2\n The rank of tree 4 in this forest is 5\n The rank of tree 5 in this forest is 37\n The rank of tree 6 in this forest is 74\n The rank of tree 7 in this forest is 214\n The rank of tree 8 in this forest is 214\n The rank of tree 9 in this forest is 670\n The rank of tree 10 in this forest is 2000\n The rank of tree 11 in this forest is 5463\n The rank of tree 12 in this forest is 12351\n The rank of tree 13 in this forest is 135151\n The rank of tree 14 in this forest is 461614\n The rank of tree 15 in this forest is 1512512\n The rank of tree 16 in this forest is 8351854\n\n\nFactorization optimizations such that of Ling, a concept that cannot be described by the old framework, are a straightforward decomposition of the \"gp\" pre-processing nodes into \"g\" and \"p\", followed by a stereoscopic combination of two such tree halves.\n\nSparseness, another concept that is difficult to understand under the old framework, arises naturally.\n\nNested sparseness, a novel concept that can reduce the circuits' logical depth, has not been discovered by prior literature due to its incompatibility with the traditional framework.\n\n\n```python\nfrom pptrees.AdderTree import AdderTree as tree\n\nwidth = 8\nt = tree(width, start_point = 214)\nt\n```\n\n\n\n\n\n\n\n\n\n\nThis framework allows for a full and efficient exploration of the entire design space.\n\nIn addition, these concepts don't just apply to binary addition. They apply to a wide range of hardware operations.\n",
"bugtrack_url": null,
"license": "Apache 2.0",
"summary": "Parallel Prefix tree generation library",
"version": "1.3.3",
"split_keywords": [
"hardware",
"adders",
"prefix"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "c1bc8b43baa38be9d81ecdd02c82acc1021bd7cdfba5d3b82942824f824b1844",
"md5": "416c463860b59b8bddc4ac79ac441aad",
"sha256": "1bac91491e3985059cd31f1be6aaba21bd5ef2002c399ed22e8066913caf3c42"
},
"downloads": -1,
"filename": "pptrees-1.3.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "416c463860b59b8bddc4ac79ac441aad",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.6.*",
"size": 62288,
"upload_time": "2023-02-07T16:51:56",
"upload_time_iso_8601": "2023-02-07T16:51:56.152633Z",
"url": "https://files.pythonhosted.org/packages/c1/bc/8b43baa38be9d81ecdd02c82acc1021bd7cdfba5d3b82942824f824b1844/pptrees-1.3.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "89e5c71160f13eb762c7d1b38937ed67e385fb7f1e05ac9828b5a8dd94ce1de5",
"md5": "917eb9b2ad43fc7bace8cf3394c94e9f",
"sha256": "57ce1b860649ce82ad6b792deaf5df4076c9c6eac08b60e103f3158d7453ec57"
},
"downloads": -1,
"filename": "pptrees-1.3.3.tar.gz",
"has_sig": false,
"md5_digest": "917eb9b2ad43fc7bace8cf3394c94e9f",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.6.*",
"size": 49317,
"upload_time": "2023-02-07T16:51:58",
"upload_time_iso_8601": "2023-02-07T16:51:58.320366Z",
"url": "https://files.pythonhosted.org/packages/89/e5/c71160f13eb762c7d1b38937ed67e385fb7f1e05ac9828b5a8dd94ce1de5/pptrees-1.3.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-02-07 16:51:58",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "tdene",
"github_project": "synth_opt_adders",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"requirements": [
{
"name": "networkx",
"specs": []
},
{
"name": "pydot",
"specs": []
},
{
"name": "graphviz",
"specs": []
},
{
"name": "Pillow",
"specs": []
}
],
"tox": true,
"lcname": "pptrees"
}
JSON
