Under Supervission of Prof. B. Alizadeh
Jan 2014-jun 2015
||Monte-Carlo Tree Search
- Work as research assistant on power-aware High level synthesis tools and high-performance low-cost machine-learning solutions
- Design and Implementation of a DSP-specific, low-power HLS tool
- Research on a Monte-Carlo Tree Search(MCTS) Based Scheduling algoritm
- Ehsan Qasemi, Mohammad H. Shadmehr, Bardia Azizian, Amir Samadi, Sajjad Mozaffari,Amir Shirian and Bijan Alizadeh, “Highly Scalable, Shared Memory , Monte-Carlo Tree Search based Blokus Duo Solver on FPGA ”, International Conference on Field-Programmable Technology (FPT), 2014.
One main challenge in High-Level Synthesis (HLS) field is the exponential run-time order of its scheduling phase. in this phase, the goal is to reach optimum scheduling of atomic operations in reasonable time.
Until now many algorithms have been introduced to obtain optimal and suboptimal scheduling, but they are mainly based on heuristic method. For instance, Force-Directed List Scheduling (FDLS), has been introduced which is one of the most efficient heuristic scheduling algorithms. This algorithm gives an optimal scheduling result from the perspective of generated hardware's latency. However, the main problem is the fact that the weight calculations required in this algorithm, have a huge computation load which makes FDLS useless for larger circuits.
To alleviate this problem, we inspire the works performed in the field of Artificial Intelligence (AI) gaming decision makings in such a way that we migrate from heuristic methods to stochastic and random simulation based methods. In such methods, instead of making a decision with weight assignment, random simulation is used. During random simulation process, suitable random decisions are made until no decision is possible to be made. At the end of the random simulation process, we can indicate whether the random decision results in success or failure. Based on such information, a global knowledge decision tree is obtained which results in more efficient as well as faster decisions to be made in comparison with heuristic methods.
Our AI-based scheduling as well as, other available scheduling algorithms have been implemented as an HLS tool in C++. The implemented scheduling algorithms include FDLS, List, FAMOS, Genetic Algorithm, etc. Our HLS tool gets CDFG generated from GAUT's output as input graph, performs scheduling, binding, and synthesizes the design in SystemVerilog language. Implemented HLS tool also considers the real synthesis results such as latency and power consumption, from design compiler for each atomic operation to get practical results.