Apparatus and method for optimizing an algorithm to convert to hardware

Abstract

Various embodiments of a method and apparatus are disclosed for creating a new device that implements an algorithm, subject to specified constraints. In some embodiments, an initial algorithm and constraints are received and converted to a new algorithm, upon which the device is based. The method further includes constructing a DAG (Directed Acyclic Graph) from the algorithm received and then reconstructing the DAG to accommodate the constraints. The method and system identify outputs that are of interest, trace the outputs of interest back to the inputs, and ignore inputs and the parts of the DAG that are not needed for generating the outputs of interest. When computing multiple jobs in parallel that each use the same DAG, portions of inputs that are shared by two parallel jobs, and portions of the DAG that compute the shared inputs are determined, and therefore only need to be computed once.

1 . A system comprising:
 a) a processor system having one or more processors; and   b) a memory system, including one or more tangible storage media, storing one or more machine instructions, which, when implemented by the processor system, cause a method to be implemented, the method including at least   (i) receiving a first Bit Coin mining algorithm at the system, the first Bit Coin mining algorithm being in a machine implementable format;   (ii) receiving one or more desired machine resource constraints at the system;   (iii) converting, by the processor system, the first Bit Coin mining algorithm to a directed acyclic graph, the first Bit Coin mining algorithm being to mine Bit Coins by solving a mathematical problem, the first Bit Coin mining algorithm being implementable on a first machine;   (iv) reconstructing, by the system, the directed acyclic graph based on the one or more desired machine resource constraints to form a reconstructed directed acyclic graph; and   (v) constructing, by the system, a second Bit Coin mining algorithm, based on the reconstructed directed acyclic graph, the second Bit Coin mining algorithm being in a machine implementable format, the memory system storing, at least temporarily, the directed acyclic graph and the second Bit Coin mining algorithm;   wherein execution of the second Bit Coin mining algorithm causes a second machine to solve the mathematical problem, based on the one or more desired machine resource constraints, solving the mathematical problem includes iterating an input value; and for each iteration of the input value computing an output value, ending the iterating when the output value meets given criteria, the given criteria being set by a Bit Coin provider, as a result of finding the output value that meets the given criteria, receiving Bit Coin;   the first Bit Coin mining algorithm including a first set of computations to compute the output value of the first Bit Coin mining algorithm from the input value and of the first Bit Coin mining algorithm, the second Bit Coin mining algorithm including a second set of computations, which when implemented by the second machine, compute the output value of the second Bit Coin mining algorithm from the input value of the second Bit Coin mining algorithm, based on the one or more desired machine resource constraints, the one or more desired machine resource constraints being one or more constraints that limit how much of a machine resource is needed by the second Bit Coin mining algorithm.   
     
     
         2 . The system of  claim 1 , wherein
 the converting of the first Bit Coin mining algorithm, including traversing the directed acyclic graph from outputs of interest to inputs that affect the outputs of interest, the outputs of interest being a subset of an output required by the Bit Coin provider; and   the method further comprising:   discarding portions of the directed acyclic graph that were not traversed.   
     
     
         3 . The system of  claim 1 , the method further comprising:
 a) dividing the directed acyclic graph into subgraphs; and   b) combining the subgraphs to reduce how many computations the second Bit Coin mining algorithm performs.   
     
     
         4 . The system of  claim 1 , the method further comprising:
 a) identifying variables of the first Bit Coin mining algorithm; and   b) converting the variables to symbolic variables.   
     
     
         5 . The system of  claim 1 , the method further comprising:
 a) identifying operators of the first Bit Coin mining algorithm; and   b) the constructing of the directed acyclic graph, including creating nodes based on the operators.   
     
     
         6 . The system of  claim 1 , the constructing of the directed acyclic graph comprising:
 a) identifying operators of the first Bit Coin mining algorithm;   b) identifying operands of the operators;   c) identifying results of the operators; and   d) matching the results of the operators with operands of subsequent operators.   
     
     
         7 . The system of  claim 1 , wherein nodes of the directed acyclic graph include operators. 
     
     
         8 . The system of  claim 1 , wherein nodes of the directed acyclic graph include symbolic variables. 
     
     
         9 . The system of  claim 1 , wherein the one or more desired machine resource constraints include a limit on how many lookup tables are in the second Bit Coin mining algorithm. 
     
     
         10 . The system of  claim 1 , wherein the one or more desired machine resource constraints include a limit on how much area on a chip is required by an integrated circuit to implement the second Bit Coin mining algorithm. 
     
     
         11 . The system of  claim 1 , wherein the one or more desired machine resource constraints include a limit on how many operators are implemented simultaneously. 
     
     
         12 . The system of  claim 1 , wherein the one or more desired machine resource constraints include a limit on a maximum delay between adjacent layers. 
     
     
         13 . The system of  claim 1 , wherein portions of the first Bit Coin mining algorithm produce an output that includes two portions; and a first of the two portions is constant and a second of the two portions changes, the second Bit Coin mining algorithm only includes inputs that affect the second of the two portions of the output. 
     
     
         14 . The system of  claim 1 , the method further comprising receiving a nonce and a block candidate, wherein the second Bit Coin mining algorithm computes an output based on the nonce and the block candidate. 
     
     
         15 . The system of  claim 14 , the method further comprising:
 a) inputting the block candidate by a conversion subgraph and converting the block candidate into a converted candidate block; and   b) inputting the nonce and the converted candidate block into a portion of the second Bit Coin mining algorithm represented by a directed acyclic graph that computes a portion of the output that changes with changes in the converted candidate block based on the nonce.   
     
     
         16 . A system comprising:
 a) a processor system having one or more processors; and   b) a memory system, including one or more tangible storage media, storing one or more machine instructions, which, when implemented by the processor system, causes a method to be implemented, the method including at least
 (i) receiving a first cryptocurrency mining algorithm at the system, the first cryptocurrency mining algorithm being to mine a publicly used cryptocurrency by solving a mathematical problem, the first cryptocurrency mining algorithm being implementable on a first mining rig machine; 
 (ii) receiving one or more mining rig machine resource constraints at the system; 
 (iii) converting, by the processor system, the first cryptocurrency mining algorithm to a directed acyclic graph; 
 (iv) reconstructing, by the system, the directed acyclic graph based on the one or more mining rig machine resource constraints, forming a reconstructed directed acyclic graph; 
 (v) constructing, by the system, a second cryptocurrency mining algorithm, based on the reconstructed directed acyclic graph; and 
 (vi) constructing a mining rig machine, the mining rig machine including an integrated circuit that implements at least a portion of the reconstructed directed acrylic graph, the mining rig machine implements the second cryptocurrency mining algorithm, wherein execution of the second cryptocurrency mining algorithm by the second mining rig machine causes the second mining rig machine to solve the mathematical problem, based on the one or more mining rig machine resource constraints, solving the mathematical problem includes iterating input values to the second cryptocurrency mining algorithm; and 
 for each iteration of the input values to the second cryptocurrency mining algorithm computing output values from the second cryptocurrency mining algorithm, ending the iterating, when the output values from the second cryptocurrency mining algorithm include a solution output that meets given criteria, the given criteria being set by a publicly used cryptocurrency provider, as a result of finding the output value from the second cryptocurrency mining algorithm that meets the given criteria, receiving the publicly used cryptocurrency, the first cryptocurrency mining algorithm including a first set of computations to compute the output values from the first cryptocurrency mining algorithm from the input values to the first cryptocurrency mining algorithm and the second cryptocurrency mining algorithm including a second set of computations, which when implemented by the second mining rig machine, compute the output values from the second cryptocurrency mining algorithm from the input values to the second cryptocurrency mining algorithm, based on the one or more mining rig machine resource constraints, the mining rig machine resource constraints being one or more constraints that limit how much of a machine resource is needed by the second cryptocurrency mining algorithm. 
   
     
     
         17 . The system of  claim 16 , the mining rig machine including version logic that determines trial input version information and candidate logic that determines values for trial nonces, the second circuit having more outputs than the first circuit;
 wherein the method further comprises,   determining a first subgraph that includes nodes of the reconstructed directed acyclic graph that are needed for computing version information from the version logic, but that are not needed for computing nonce information;   determining a second subgraph that includes nodes of the reconstructed directed acyclic graph that are needed for computing nonce information from the candidate logic, but that are not needed for computing the version information;   determining a third subgraph that includes nodes of the directed acyclic graph that are needed for computing both nonce information and version information;   determining nodes of the directed acyclic graph that are needed for computing the nonce information and the version information;   the constructing of the cryptocurrency mining rig machine
 constructing a first circuit that implements the first subgraph; 
 constructing a second circuit that implements the second subgraph; 
 constructing a third circuit that implements the third subgraph; 
 outputs of the first circuit being connected to inputs of the third circuit; 
 outputs of the second circuit being connected to inputs of the third circuit; 
 each output of the first circuit generating, via the third circuit, a different trial solution of the problem and each output of the second circuit generating, by the third circuit, a different trial solution of the mathematical problem; and 
   the integrated circuit including at least the third circuit, wherein the version logic changes the version information more frequently than the candidate logic changes the nonce information.   
     
     
         18 . The system of  claim 17 , the output of each first circuit being connected to multiple third circuits. 
     
     
         19 . A method comprising:
 a) receiving, at a system, a first algorithm, the system including at least
 (i) a processor system having one or more processors and 
 (ii) a memory system, including one or more tangible storage media, storing one or more machine instructions, which, when implemented by the processor system, causes the method to be performed; 
 the first algorithm being in a machine implementable format, the first algorithm computing multiple hash values in parallel, the first algorithm receives constant values and a nonce, processing the nonce and the constant values by a first phase of a constellation of the first algorithm, output of the first phase and shared logic are received at, and processed by, a second phase, output of the second phase being input to a third phase, output of the third phase being 64 bits of a hash, executing each constellation including executing at least 942 additions; 
   b) receiving, by the system, one or more desired machine resource constraints;   c) converting, by the processor system, the first algorithm to a directed acyclic graph, the first algorithm being to mine a cryptocurrency by solving a mathematical problem, the first algorithm being implementable on a first machine;   d) reconstructing, by the system, the directed acyclic graph based on the one or more desired machine resource constraints; and   e) constructing, by the system, a second algorithm, based on a directed graph, the second algorithm being in a machine-implementable format, wherein execution of the second algorithm by a second machine causes the second machine to solve the mathematical problem, based on the one or more desired machine resource constraints, solving the mathematical problem includes iterating an input value; and for each iteration of the input value computing an output value, ending the iterating when the output value meets given criteria, the given criteria being set by a cryptocurrency provider, as a result of finding the output value that meets the given criteria, receiving the cryptocurrency, the first algorithm including a first set of computations to compute the output values from the input values and the second algorithm including a second set of computations, which when implemented by the second machine, compute the output value from the input value, based on the one or more desired machine resource constraint, the one or more desired machine resource constraint being one or more constraints that limit how much of a need the second algorithm has for a machine resource, output of the second algorithm being the same as the output of the first algorithm.   
     
     
         20 . The method of  claim 19 , further comprising:
 the converting of the first algorithm, including traversing the directed acyclic graph from outputs of interest to inputs that affect outputs of interest, the outputs of interest being a subset of outputs required by the cryptocurrency provider, which is part of the output value; and   discarding portions of the directed acyclic graph that were not traversed.