Open tripack45 opened 7 years ago
//
// Created by king on 17-4-10.
//
#ifndef VE490_BOOL_FUNCTION_H
#define VE490_BOOL_FUNCTION_H
#include <vector>
#include "kmap.h"
#include "../../circuit_profile/sim_profile.h"
/* We need to first clarify the concept of a "Boolean Function"
* This involves clearifying 2 things
*
* 1. Internally, what is the REPRESENTATION of a "BooleanFunction"
* 2. Externally, what should be an operation of a "BooleanFunction"
*
* When handling both, the following question are need to be taken
* into consideration
* 1. Performance. How often does the structure be used? How will it
* be used? Will it be constantly copied over? Is it better to
* make it smaller in size, or it could be a very large class.
* What REPRESENTATION would make the common accessing methods
* quicker
*
* 2. Making Sense. Operations, states should be intuitive.
*
* I would argue that in my imagination a Boolean function is a
* such a construct: It maps boolean inputs into a boolean space,
* and it is named, namely you name the arguments.
*
* I guess two concepts are needed to be differentiated upon. The
* boolean function that you see in mathematics,
* i.e. input-truthTable-output, is not the same "BooleanFunction"
* that you printed out into the blifFunction. The thing that you
* print into the file, it is a tree-like structure, It doesn't
* care what its final truthtable is, just simply the tree-like
* structure. However the actual BooleanFunction, the thing that
* you perform operations on, cares a lot.
*
* In light of this observation. My suggestion would be giving them
* a separate treatment. Please see the final sections for details.
*
* Since we are naming the inputs so the class would be pretty heavy
* weight. It has a significant cost of contantly copying those node
* names. So I would like to avoid copying it too much.
*
* This actually gives us two things:
* 1. First since we are not copying it very often we could keep more
* information than needed (even redundant ones) as long as it
* makes accessing easier
* 2. Better not to implement all those XORs ANDs in this class (since
* the value semantic doesn't go well with the fact that this class
* is heavy in weight). Which implies we probably need something
* that is more lightweight, and easier, and faster to perform the
* xors, ands, count_ones, sort of operations.
*/
class BoolFunction {
private:
int inputSize;
std::vector<int > truthTable; // consist of 0/1
/* A TruthTable is probably something worth encapsulating.
* TruthTables are often operated on.
* */
std::vector<std::string > portName;
FocusedSimulationResult simRes;
int divideMode; // e.g. divideMode = XOR_IGNORE
/* Above two are examples of being not intuitive.
* Because two functions are equivalent as long as
* they have the same truth table and same input
* ordering (which corresponds to your portName)
* It doesn't make sense that "Simulation result" is
* a decisive of a function. The same argument also
* applies to divideMode. These information probably
* needed to be kept outside the class.
* It makes even less sense that by doing so you will
* be COPYING the same simulation information in
* multiple boolean functions, which does not make sense
* results into multiple objects. */
public:
/* You could probably use a structure called "partition" to replace
* these two arguments. */
Kmap buildKmap(std::vector<std::string >, std::vector<std::string >);
BoolFunction combineWith(const BoolFunction& a, const int& opera);
/* I'm not sure how this will be used so I make no comment (except this) */
bool divideAble();
/* If your class only contains STL containers, you actually
* don't need write your own copy constructors / assignment
* operators. Due to the "rvalue reference" and "move semantic"
* It is not even suggested to write so (if you just use STL
* containers as your attributes. If you insist to do so make
* sure you write all 5 functions, and in correct form.
* */
void operator= (const BoolFunction& initFun);
// Return value should be BooleanFunction&
// Assignments return left values.
/* I don't understand. How come a Boolean function has "Multiple"
* truthtables? How does it make sense that "I want the third
* truthTable". How do you represent a truthTable by a single
* integer? */
int operator[] (const int& i); // return one of its truthtable
/* I actually won't put this here. Since your function has
* named arugments. What will be the new name of arguments if
* you XOR it with some function else? */
int operator^ (const BoolFunction& initFun);
/* Equivalence operator lookds fine */
bool operator== (const BoolFunction& initFun);
/* Constructors should not be written in this manner
* Constructors must gurantee that as long as it suceeds.
* Now if I use BoolFunction() to construct the object
* the object could be in a invalid state. Meaning how do
* you define the "default" value for a boolean function?
* How many input ports? What are their default names?
* What is its default truthtable? And more fundamentally why
* do you need a default BooleanFunction? The idea is, if the
* answer to any of above questions are false (non-exists).
* then you cannot allow this object to be default-constructable,
* which means the first function cannot exists. If in any
* situation you find to self needing it (while the default
* construction doesn't make sense), you probably are
* making a mistake somewhere. You either confused some idea
* or you are writing wrong logic. */
BoolFunction();
BoolFunction(std::vector<int > truthTable, std::vector<std::string >, FocusedSimulationResult simRes);
// Again simulation results are probably not needed.
~BoolFunction();
/* You can't critisize print functions, can you? */
void displayName();
void displayWhole();
};
// ==============================================
// ============= My modifications ===============
// ==============================================
#endif //VE490_BOOL_FUNCTION_H
#ifndef VE490_ALGORITHM_HEADER_H
#define VE490_ALGORITHM_HEADER_H
// A notion of "Algorithm"
// An algorithm is essentially a "function"
// A function has parameter (constructor aruguments)
// An list of arguments (operator()'s arguments)
// A return value (operator()'s return value)
class AlgorithmDecompose {
private:
// Private Type
// Intermedia values, etc.
// Actually you only need to declare them here
public:
// Public Typs
// This is the return value type
// A struct is fine. No need for private attributes etc.
// it's just data, that's it, and you n
struct Result {
// What is the return of a decomposition?
BooleanFunction approxFunction;
// The function after approximation
BlifBuilder blifBuilder;
// Information related to build a boolean function
};
private:
// Private Methods & Algorithm global states
// Private methods are helpers.
// Algorithm global states is the "shared information"
// between different stages of algorithm execution
public:
// Public Methods
// These 2 are only
AlgorithmDecompose();
Result operator()(const BooleanFunction& fun,
const SimulationResult& simData);
// These two should be the only 2 methods exposed
// Since for a "function" we only require it is callable.
// Mark copy/move methods as "delete"
// This means we don't NEED them
// Any attempt to invoke them triggers a COMPILE ERROR
AlgorithmDecompose(const AlgorithmDecompose&) = delete;
AlgorithmDecompose(AlgorithmDecompose&&) = delete;
AlgorithmDecompose& operator=(const AlgorithmDecompose&) = delete;
AlgorithmDecompose& operator=(AlgorithmDecompose&&) = delete;
};
class BooleanFunction {
};
class KMap {
};
#endif //VE490_HEADER_H
BooleanFunction { inputSize, inputName, TruthTable}
(BooleanFunction, DecompositionInfo) AlgorithmDecomposition()(BooleanFunction, SimulationResults)
TruthTable {}
BooleanFunction {inputSize, inputName, TruthTable}
KMap {}
DecompositionInfo { Map< (nodeName, nodeName ) -> (nodeName, Method)> }
AlgorithmDecompose {}
typedef std::string nodeName;
class DecompositionInfo
{
struct connection
{
nodeName n1;
nodeName n2;
TruthTable method;
} std::map<nodeName, connection> data;
nodeName outputNodeName;
friend DecompositionInfo
combineDecompositionInfo(const DecompositionInfo & d1,
const DecompositionInfo & d2,
const TruthTable& table,
const nodeName& newOutput);
public:
DecompositionInfo(nodeName name, bool flip=false);
nodeName outputNodeName();
void exportBlif(const std::string& filename);
std::set<nodeName> outputName();
}
combineDecompostitionInfo(const DecompositionInfo & d1,
const DecompostitionInfo & d2,
const TruthTable& table
const nodeName& newOutput);
typedef boost::dynamic_bitset<> dyBitset;
class TruthTable {
size_t inputSize;
public:
TruthTable cofactor(size_t input, bool = true);
friend combineTruthTable(TruthTable t1, TruthTable t2,
dyBitset t1Mask, dyBitset t2Mask);
int operator[](size_t term);
int operator[](dyBitseet term);
byBItset diff(TruthTable table);
KMap getKMap(std::vector<int> node1,
std::vector<int> node2);
TruthTable project(std::map<int, int> condition,
std::vector<int> onList);
size_t nInputs();
}
class BooleanFunction {
private:
int inputSize;
TruthTable truthTab;
std::vector<std::string> portName;
std::string outPortName;
public:
BooleanFucntion(const int &inputSize,
const TruthTable& truthTab,
const std::vector<std::string>& portName,
const std::string& outPortName);
~BooleanFunction();
bool opeator == (const BooleanFunction &initBF);
int operator^(const BooleanFunction &initBF);
int getInputSize();
int getVal(const dyBitset& term);
int getVal(const size_t term);
std::string getPortName(const int& i);
std::string getOutPortName();
}
class Kmap {
private:
int width, height;
std::vector<TruthTable > kmap;
std::vector<std::string > widthName;
std::vector<std::string > heightName;
public:
struct BestApprox {
BooleanFunction leftFunc;
BooleanFunction rightFunc;
int errorCount;
combineMethod method;
}
Kmap(const BooleanFunction& BF, std::vector<std::string > widthName, std::vector<std::string > heightName);
~Kmap();
bool operator== (const Kmap& initKmap);
int operator^ (const Kmap& initKmap);
TruthTable operator[] (const int& i);
BestApprox divide();
int getWidth();
int getHeight();
std::string getWidthName(const int& i);
std::string getHeightName(const int& j);
}
class AlgorithmDecompose {
public:
std::deque<BooleanFunction> BooleanFunctionPool;
// typedef DecompositionInfo ResultType;
struct ResultType {
size_t errorCount;
DecompositionInfo deInfo;
//BooleanFunctionPool bfPool;
}
private:
ResultType bestDecomp;
void searchPrcoe(BooleanFunctionPool bfPool, DecompositioInfo deInfo);
public:
ResultType operate(const BooleanFunction& initBF,
const SimulationResult& simData);
AlgorithmDecompose();
~AlgorithmDecompose();
}
void searchProce(....) {
if select one that can decompose for bfPool == true
then -->x
else { compare deInfo with Result; }
for all x's decomposition {
decompose x;
BooleanFunctionPool newBFPool = bfPool + x's decomposed functions - x.
DecompositionInfo newDecompInfo = deInfo + x's decomposition;
searchProce(newBFPool, newDecompInfo);
}
}
void searchProce(....) {
if select one that can decompose for bfPool == true
then -->x
else { compare deInfo with Result; }
for (decomposition in x's decomposition) {
set<InputName> leftNode = decomposition.leftInput;
set<InputName> rightNode = decomposition.rightInput;
(LeftBooleanFun, RightBooleanFun, CombineMethod) = Decompose x;
bool lrelavent = LeftBooleanFun.isRelevant();
bool rrelavent = RightBooleanFun.isRelavent();
if (lrelavant && rrelavent) {
(LDecomposeInfo, LApproximatedFunction) = searchProce(LeftBooleanFun);
(RDecomposeInfo, RApproximatedFunction) = searchProce(RightBooleanFun);
return ( combine(LDecomposeInfo, RDecomposeInfo, CombineMethod),
FunctionCombine(LApp., RApp,. Mask...));
}
}
}
目前提交了一部分,你看到了的话可以看一下。 然后TruthTable 和 DecompositionInfo 那里可能得你维护了。 我已經把AlgorithmDecomposition写掉了,应该没错才对。 然后Kmap和BooleanFunction,感觉依赖你的TrtuthTable,暂时不好下手。 然后说这样几个问题。
/home/tripack/490_core/newApprox/src/algorithm_decompose.cpp:34:20: error: use of deleted function ‘AlgorithmDecompose::ResultType::ResultType()’
ResultType res;
/home/tripack/490_core/newApprox/src/algorithm_decompose.h: In constructor ‘AlgorithmDecompose::AlgorithmDecompose()’:
/home/tripack/490_core/newApprox/src/algorithm_decompose.h:39:26: error: no matching function for call to ‘BooleanFunction::BooleanFunction()’
AlgorithmDecompose() {}
这两个问题都是同一个原因引起的,就是如果你的类没有默认构造函数,那么根据显然所有蕴含了这个类的实例的结构体/类都不会有默认构造函数。然后当你尝试声明他们的实例的时候,就会发现缺少默认构造函数,导致错误。一种解决办法是在BooleanFunction
和 TruthTable
上加默认构造函数。但是这个不是很好。因为没有默认构造函数其实是一种保护措施,它会防止你使用未初始化的值。 一般的办法是在最高层次的,不得不默认构造的类型上加默认构造函数,也就是说默认构造函数加在 AlgorithmDecomp
和 AlgorithmDecompose::ResultType
这两个类型上面。
然后关于这个MajorRow的问题,我想到了一组理论,需要调整一下我们的算法,新的算法是:
我会提供理论上的解释的,这里不是很写的下。我可能直接敲成Latex了。
现在我这里说一下我的进度。 码完了。能编译,测试没上过。 然后kmap.divide()这个东西写的很长,很长的原因是因为 结构上其实就是这么复杂,因为本来就有四个cases要去分别算,虽然每者都是类似的但是小差别比较多,而且容易产生很麻烦的调用,想了想就全码了,没怎么做大的抽象(我怕做了变成像上次的approx那样逻辑链太长),中间用到了三个帮助的函数。
同时,我使用的是你的算法,只是一开始没有随机一个majorrow,而是把所有的行算了一个majorrow。反正我理解了一下,我觉得你的精髓在于重复23两步,我这点上没有改变。然后你的意思我大概是能理解的,直观上的感觉是有的。然后如果一定要随机的话和我讲一下我改。
那些因为构造的问题我在最上层的结构里加了基本的那种构造函数,反正是瞎构造的你懂的。然后确定一下copy constructor的存在性吧,我觉得这个东西很重要。
大概就是这些了。然后const之类的问题我好像也改得差不多了。。至少能编译了吧
[100%] Built target newApprox
写在这里你能看见:
以上。我休息了。
目前,把BoolFunction测掉了,然后mffc过了一遍,为了测试用。 Kmap和BoolFunction的小错误改了蛮多,目前基本上能保证除了divide部分的正确性。 其中BoolFunction是实测的,Kmap做了一边review。
有两个严重问题,一个需要你帮忙,一个需要你这里的协调:
Linking的问题是 Linking是有顺序的,假设你有3个library: a.lib, b.lib, c.lib 如果 a.lib 用了 b.lib 和 c.lib 的函数, a就必须出现在b c前面.
关于顺序问题的最终说法: 问题的核心在于由string构造BitSet的过程中,会把String但做一个大整数的二进制表示. 比如 "1010"会当作整数 0xA 的二进制表示. 然后 Bitset的访问是,比如访问 Bitset[2]的时候,访问的是这个大整数的二进制表示的,从最小权重的位数起,第二位的,也就是读出来是1.
使用DBitset进行访问有很明确的语义. 如果你的位序是 {x1, x2, x3} 这么初始化的, 如果你的Bitset是 {b[0] = 0, b[1] = 1, b[2] = 1} 是1, 那么你就是访问 {x1 = 0, x2 = 1, x3= 1}这个case.
但是这个语义对于真值表感觉很奇怪. 最终经过考虑我想这么处理.
DBitset
进行构造,不要使用string. DBitset
有已经写出来的一系列方便的函数. 应该用起来很顺手才是. 而且能少写很多循环.
经过考虑,我感觉Approx部分最大的问题是“全局状态”和本地状态的不清晰。
目前代码从形式上看,表现为函数传入和传出参数相当复杂,我考虑了一下比较根本的原因应该是,函数访问一些全局状态的时候,不应该自己传入参数,而是应该设计某种全局状态。
所以首先,算法本身应该设计成 Functor. 然后把全局状态作为成员函数,然后用构造函数初始化全局状态。比如求一个数组最小值并且返回它的最小下标的函数应该设计成
还有就是,KMap这样的类不应该把算法作为它的成员函数。KMap类是一种容器,比如你可以要求它返回某一行,或者返回某两行的差值。然后算法利用这些接口进行操作,获得结果。
初步想法是,我来重写KMap这里的东西。