Alp Gorker

Arda Malazgirt
email: alp.malazgirt@boun.edu.tr

Yurdakul
email: yurdakul@boun.edu.tr

Smail Niar
email: sniar@univ-valenciennes.edu

MIPT: Rapid Exploration and Evaluation for Migrating Sequential Algorithms to Multiprocessing Systems with Multi-Port Memories

Keywords: Instruction Level Parallelism, Genetic Algorithm, Optimization, Measurements

Research has shown that the memory load/store instructions consume an important part in execution time and energy consumption. Extracting available parallelism at different granularity has been an important approach for designing next generation highly parallel systems. In this work, we present MIPT, an architecture exploration framework that leverages instruction parallelism of memory and ALU operations from a sequential algorithm's execution trace. MIPT heuristics recommend memory port sizes and issue slot sizes for memory and ALU operations. Its custom simulator simulates and evaluates the recommended parallel version of the execution trace for measuring performance improvements versus dual port memory. MIPT's architecture exploration criteria is to improve performance by utilizing systems with multi-port memories and multi-issue ALUs. There exists design exploration tools such as Multi2Sim and Trimaran. These simulators offer customization of multi-port memory architectures but designers' initial starting points are usually unclear. Thus, MIPT can suggest initial starting point for customization in those design exploration systems. In addition, given same application with two different implementations, it is possible to compare their execution time by the MIPT simulator.

I. INTRODUCTION

Today, there is significant research for developing new platforms for large scale concurrent and distributed systems. Most of the research aims towards increasing scalability by raising the abstraction levels and providing simplicity to develop and maintain code. Hence, the single computing block (node, actor etc.) performance of these large scale systems has remained inefficient due to poor system level design decisions and/or unoptimized code [START_REF] Yang | Nativetask: A hadoop compatible framework for high performance[END_REF]. In addition, different platforms have different compute node characteristics, such as shared threads or dedicated single thread per node.

Building more powerful compute units has been suggested in [START_REF] Pavlo | A comparison of approaches to large-scale data analysis[END_REF]- [START_REF] Verma | Breaking the mapreduce stage barrier[END_REF] for increasing scalability and reducing node inef-ficiency problems in future large scale processing systems. A recent publication [START_REF] Hameed | Understanding sources of inefficiency in general-purpose chips[END_REF] suggests more aggressive use of instruction extensible processors at compute nodes of large scale processing systems in order to tailor application for improved performance and efficiency. Authors target three different parts of the processor architecture: the instruction decoders, register files and the data paths. For memory intensive applications, authors consider reduction of load/store operations as major contributors to performance improvements. They have shown that overall performance have improved by reduction of data load/store by using multi-port register file. In addition, short lived data was stored in custom buffers instead of register files which prevent unnecessary register file accesses. This short lived data also decrease space in the register file for nonintermediate data and causes additional memory load/stores, thus performance is decreased. However, it is known that increasing port numbers affects area dramatically which affects power consumption negatively [START_REF] Tatsumi | Fast quadratic increase of multiportstorage-cell area with port number[END_REF], [START_REF] Zuo | An intelligent multi-port memory[END_REF]. This issue has become more important with the advent of processor architectures with multi-port memories [START_REF]Alpha Architecture Handbook[END_REF], [START_REF] Chen | Cell broadband engine architecture and its first implementationa performance view[END_REF].

In this paper, we present the architecture and underlying heuristics of MIPT (Million Memory Instructions Per Trace) framework which has built its foundations from the aforementioned discussion. It processes sequential algorithm execution traces for architecture exploration and extracts parallelism for memory and Arithmetic Logic Unit (ALU) operations. MIPT heuristics explores the design space and decides the number of read/write ports for memory operations and the number of issue slots for ALU operations. In addition, it recommends a new schedule that exploits the suggested port and issue slot number. MIPT aims to improve instruction level parallelism (ILP) by first analyzing memory load/store instruction traces and true register data dependencies a between memory instruca True register data dependency is defined as dependency between registers due to data flow, reading a value of register after writing it. tions. Our analysis algorithm extracts maximum and average instruction level parallelism. Multi-port memory number and issue slot sizes are determined by maximum parallelism. Our recommendation algorithm explores design space and reduces maximum port usage and issue slot size. Hence, we gain significantly from resource usage while keeping the same performance. This is achieved by reordering some instructions to different access steps, thus lowering maximum parallelism. Nevertheless, we try to preserve average parallelism, which is defined as the average number of instructions per access step.

Our primary contributions are:

• A rapid analysis method that extracts memory level parallelism of memory instructions and instruction level parallelism of ALU operations. The method is based on bundling load/store instructions together without creating any data hazards. This lowers the number of accesses to memory and exploits multi-port memory structures. After memory operations are bundled, arithmetic operations are bundled and scheduled in the same way. • An evolutionary algorithm that reduces maximum memory port usage which gains significantly from resource usage but keeping the similar degree of parallelism and performance. This is achieved by re-scheduling some instructions, thus improving average parallelism without increasing the execution time. • A custom simulator that evaluates the performance of the recommended architecture. In addition, MIPT simulates and reports the execution time given algorithm's execution trace, read/write port and ALU slots size.

The main practical application and usefulness of MIPT framework is providing a starting point for migrating sequential applications to multiprocessing systems with multi-port memories. Given a real sequential application, MIPT finds out how it can be parallelized. MIPT framework does not implement any hardware architecture. MIPT analyzes any sequential application, finds average and maximum parallelism, searches the design space and recommends designer memory port and issue slot size. There exists design exploration tools such as Multi2Sim and Trimaran [START_REF] Ubal | Multi2sim: A simulation framework to evaluate multicore-multithread processors[END_REF], [START_REF] Chakrapani | Trimaran: An infrastructure for research in instruction-level parallelism[END_REF]. These simulators offer customization of multi-port memory architectures but require a huge execution time for exploring the different configurations. Thus, our tool can suggest initial starting point for customization in those design exploration systems. In addition, given same application with two different implementations, it is possible to compare their execution time by our custom simulator. It is known that coding style, compiler optimizations and different compilers generate different binaries. Conversely, given an algorithm, its input data, read/write port size and multi-issue ALU structure, it can simulate and suggest a schedule which minimizes execution time

The rest of this paper is organized as follows. We discuss related work in literature and a use case where a framework like ours could be used in Section II. Section III explains the architecture and the stages of the framework. Experimental results are presented in Section IV. Section V includes our discussion of potential MIPT use cases and our conclusion.

II. RELATED WORK

We have identified three areas where parallelism is exploited, thus relate to our work:

Compilation Techniques Software compilation techniques based on traces and profiles have been studied widely [START_REF] Fisher | Trace scheduling: A technique for global microcode compaction[END_REF] [13] [START_REF] Lam | Software pipelining: An effective scheduling technique for vliw machines[END_REF] [15] [START_REF] Allan | Software pipelining[END_REF]. Parallelizing compilers for VLIW processors provide ILP by formatting more than one operations as one instruction at compile time. VLIW compiler prevents implementing dependency checking, structural hazard checking and complex instruction dispatch hardware. All these are figured out by the compiler. Software pipelining, trace scheduling, predicated execution, hierarchical reduction and speculative execution have been major compiler optimizations. Trace scheduling [START_REF] Fisher | Trace scheduling: A technique for global microcode compaction[END_REF] required additional code when operations are reordered. Speculative execution [START_REF] Smith | Boosting beyond static scheduling in a superscalar processor[END_REF] helps the reduction of compensation code and moves instructions past branches. The speculatively executed code shouldn't produce any stalls to the processor pipeline when it is not needed. Speculative execution can be implemented as hardware or software. Software pipelining [14] [16] aims at compacting loop kernels by minimizing initiation intervals. Predicated execution [START_REF] Hsu | Highly concurrent scalar processing[END_REF] aims to convert branches to basic blocks with hardware defined predicates on certain instructions. The predicated execution simplifies compilation due to reducing branch code and avoid branch prediction but predicated instruction are always fetched whether or not they are executed. Hierarchical reduction [START_REF] Lam | Software pipelining: An effective scheduling technique for vliw machines[END_REF] is the method to simplify scheduling process by compacting and representing scheduled program components as a single component. This component is consisted of having the aggregate resource and scheduling constraints of the scheduled program components. Approaches that extract ILP parallelism that do not work with execution traces require dependency analysis methods such as Omega test [START_REF] Pugh | The omega test: a fast and practical integer programming algorithm for dependence analysis[END_REF], GCD test [START_REF] Maydan | Efficient and exact data dependence analysis[END_REF] and points-to-analysis [START_REF] Wilson | Efficient context-sensitive pointer analysis for C programs[END_REF] which are computationally expensive. MIPT heuristics analyze execution traces where all the address and register dependencies can be checked via real memory addresses and registers generated in the traces by only iterating over the control and data flow graph (CDFG). Therefore, all of the data dependency and structural hazards can be solved allowing code movement above branches if branch is known to be not taken under provided input data. This analysis is explained in the next section.

Parallelism extraction and classification: Parallelism extraction/classification from applications are used in application specific processor design and measurements of software metrics [START_REF] Cabezas | Parallelism and data movement characterization of contemporary application classes[END_REF] [START_REF] Jordans | Exploring processor parallelism: Estimation methods and optimization strategies[END_REF]. Work in [START_REF] Cabezas | Parallelism and data movement characterization of contemporary application classes[END_REF] presents methods for measuring available instruction level and thread level parallelism in different classes [START_REF] Asanovic | The landscape of parallel computing research: A view from berkeley[END_REF] of applications. Results show that applications which are in the same class do not possess same ILP and TLP parallelism. In addition, TLP and ILP do not necessarily correlate. Applications with low ILP might have high TLP. However, thread level analysis and task partitioning depends highly on the underlying communication structures. Our framework leverages instruction level parallelism from sequential algorithms. It does not support any thread level parallelism extraction. Work in [START_REF] Jordans | Exploring processor parallelism: Estimation methods and optimization strategies[END_REF] introduces force based parallelism on basic blocks to measure VLIW processor issue width. Force based parallelism calculates possible availability of operations in a time interval inside basic blocks by keeping distribution graphs. Inter iteration dependence of loops are broken with introduction of local variables. However, handling of branches with distribution graphs are known to generate poor results, because some paths can be favored probabilistically [START_REF] Fisher | Trace scheduling: A technique for global microcode compaction[END_REF]. Conversely, MIPT processes execution traces and no paths are favored. All existing paths in the given trace are processed by our heuristics. Nevertheless, if a possible branch path is not executed, it is not processed.

Cache replacement Policy and Scratchpad memory utilization: Parallelization of memory instructions is a determining criteria when designing new cache replacement policies. The work in [START_REF] Qureshi | A case for mlp-aware cache replacement[END_REF] proposes a DRAM cache replacement policy in out of order superscalar processors based on parallelism cost and occurrence time of parallel memory operations. Additionally, policy switch is possible based on hardware based sampling. Similarly Data Trace Cache [START_REF] Ramaswamy | Data trace cache: An application specific cache architecture[END_REF] inserts an application specific cache with data locality improving cache placement function. This improves hit rates in tree based applications because conflict sets are allocated based on tree levels. So memory is divided accordingly based on level cardinality. Similarly, parallelism of memory instructions is exploited for efficient allocation and utilization of scratchpad memories (SPM) where it coexists with caches. The heuristics developed in [START_REF] Salamy | An effective solution to task scheduling and memory partitioning for multiprocessor system-on-chip[END_REF] the required scalar variable data size, access frequencies and execution time of block sizes for maximizing scratchpad utilization. Similarly, our recommendation algorithm can be used in allocation and utilization of SPM in embedded systems domain. Based on the available port requirements, our recommendation algorithm tries to extract parallelism while lowering the number of accesses.

III. FRAMEWORK ARCHITECTURE

MIPT framework is divided into four stages as shown in Figure 1. First step is profiling of the algorithm. Application execution traces and data dependency graph are created from given input data set and program binary. It is explained in Section III-A. Second step of MIPT is the analysis of traces. In the analysis section, analysis algorithm applies certain rules to traces and the trace is reordered according to the rules. Thus, a new reorder of traces, maximum parallelism and average parallelism are generated. These results are fed to recommendation algorithm which is the third step. The details of the analysis algorithm is explained in Section III-B. The recommendation algorithm aims to reduce maximum memory port and issue slot size usage without decreasing average parallelism.

A. Extracting and Formatting ExecutionTraces

Traces are generated from the application binary and given input data set. Our trace generation program uses PIN [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF] library and x86 application binaries are compiled from C/C++ source files. The traces are stored in MIPT's local database.

B. Parallelism Analysis from Execution Traces

Our analysis algorithm processes traces to extract parallelism. To extract maximum parallelism, at the beginning, we assume that there are a sufficient number of internal registers. Register renaming is employed to prevent structural hazards. The analysis is concerned with reordering and bundling instructions without breaking data dependencies. Hence, the reordering logic is developed under certain rules.

• A set of n instructions M = {I 1 , I 2 ....., I n } with execution times {p 1 , p 2 , ...., p n } • For I i , I j ∈ M, A s ∈ N, k ∈ N, and t ∈ {read, write}; the quadruple I i , A s , t, k denotes the kth occurrence (access step) of I i at address A s which is a read or a write instruction • For all k > 0 such that: 1) I i , A s , write, k +1 cannot start before or at the same time with I j , A s , write, k 2) I i , A s , read, k + 1 cannot start before or at the same time with I j , A s , write, k 3) I i , A s , write, k +1 cannot start before or at the same time with I j , A s , read, k

The algorithm applies these rules to each load/store instruction. The instructions that satisfies these rules exploit instruction parallelism without breaking data dependencies. Rule 1, 2 and 3 are concerned with data hazards that may happen when write and read to same address occur by different instructions. The original order read from the trace files is not changed in order to preserve data dependency. Rule 3 also handles register data dependency. All the rules are checked in a single pass of memory instructions. We define the reordering problem as the reordering of instructions based on the given rules and finding their execution start time. Definition 1. A reordering α of all the given instructions M and ∀k > 0; S α Ii,A,t,k is the start time of I i , A, t, k based on given reordering rules.

Instructions with the same start times are parallel and are scheduled at the same access time. This reordering extracts the maximum parallelism which is defined as the highest number of instructions in an access step. The algorithm 1 shows how the reordering logic rules are applied to traces. The input of the algorithm are execution trace list and data dependency graph. The algorithm iteratively compares instructions and bundles them to access steps according to the reordering logic. The output of the algorithm is the reordered trace list, average parallelism and maximum parallelism obtained from the trace.

C. MIPT Outputs 1) Reporting Metrics: MIPT prepares the following metrics: total number of registers used, memory port size, ALU issue size, ALU issue structure, average parallelism, maximum parallelism, estimated execution cycle, estimated average number of memory accesses (number of bundles), estimated average non-memory accesses (number of ALU bundles). These information yield explorations and comparisons between different algorithms or different versions of the same algorithms.

2) Recommended Schedule Generation: MIPT produces recommended schedule for the explored configuration. The recommended schedule is the new reordered trace file. The trace file can be explored through MIPT's user interface.

D. An Evolutionary Algorithm for Reducing Maximum Parallelism of Instructions

Maximum parallelism information extracted from analysis algorithm is important because fastest execution requires maximum parallelism. However, implementations based on maximum parallelism will be inefficient in terms of area and power consumption. The recommendation algorithm reduces maximum port usage and issue slot size. Hence, we gain significantly from resource usage while keeping the performance attained at maximum parallelism. This is achieved by reordering some instructions to different access steps, thus lowering maximum parallelism. The algorithm is based on a genetic algorithm (GA) in the literature [START_REF] Alp | An efficient genetic algorithm for the p-median problem[END_REF]. We have selected this method because the access step and instruction encoding could be converted to GA chromosome encoding without much effort. In addition, GA can solve multi solution problems because of its population concept.

Recommendation algorithm extracts instruction level parallelism. We have chosen to limit the issue size to the maximum number of read/write port number of the multi-port memory. For example, 3R 1W configuration is assumed to have less than or equal to four issue slots. Overall execution time can be improved by employing different parallelisms such as thread level parallelism or multi-core parallelism in addition to instruction level paralellism. Moreover, future 3D memory chips such as work in [START_REF] Lim | 3d-maps: 3d massively parallel processor with stacked memory[END_REF] are multi-port, supports 4R 3W configuration and are faster than current dual port DRAM memories.

Solution Encoding: Solution encoding is designed as one dimensional array. Each element of the array represents an instruction. This array is called an individual and each instruction is a gene of the chromosome. For example, given a chromosome (1,3,2,2), it is understood that there are four instructions and first instruction executes at access step one, second instruction is at step three and the rest is at step two. A solution is feasible if it does not violate any dependency rules explained in Section III-B.

Fitness Function: The fitness of a chromosome is identical to the objective function value of the solution. The objective is to minimize the maximum number of instructions in an access step without increasing the total access steps and creating any data hazards. All the reordering has to satisfy data dependencies, otherwise the solution is considered infeasible.

Population Size: There is a trade-off in evolutionary algorithm design. Large population sizes are slower than small population sizes. However, small population sizes may not generate enough diversity. In order to balance speed and diversity we limit an instruction to be reordered in a predetermined number of access steps. This is called access step window (ASW). Let n being number of selected access steps which have instructions more than initial average parallelism and a being the highest number of access step window (ASW). ASW is determined from dependency graph by checking inter iteration dependencies in the loops if there are any. ASW is bounded to 10 as the maximum value. Finally, The population size is calculated as: p(n, p) = max 2, ln(n * a) a * 10 * log(n) Initialization of the Population and Selecting Parents: New orders and parent selection are generated randomly until the population size is filled. Infeasible, solutions are not kept in the population pool.

Generating New Members: A new member is generated by crossover method from two parents that are chosen randomly from the pool. The crossover happens from a randomly chosen point of the genes. Nevertheless, the crossover point should not violate data dependency. For example, two parents that are selected from the pool are [START_REF] Yang | Nativetask: A hadoop compatible framework for high performance[END_REF][START_REF]Big data handbook[END_REF][START_REF] Pavlo | A comparison of approaches to large-scale data analysis[END_REF][START_REF] Hameed | Understanding sources of inefficiency in general-purpose chips[END_REF][START_REF] Verma | Breaking the mapreduce stage barrier[END_REF][START_REF] Tatsumi | Fast quadratic increase of multiportstorage-cell area with port number[END_REF] and [START_REF] Pavlo | A comparison of approaches to large-scale data analysis[END_REF][START_REF] Pavlo | A comparison of approaches to large-scale data analysis[END_REF][START_REF]Big data handbook[END_REF][START_REF] Tatsumi | Fast quadratic increase of multiportstorage-cell area with port number[END_REF][START_REF] Hameed | Understanding sources of inefficiency in general-purpose chips[END_REF][START_REF] Verma | Breaking the mapreduce stage barrier[END_REF]. If crossover index is three, offsprings become (1, 3, 2, 6, 5, 4) and [START_REF] Pavlo | A comparison of approaches to large-scale data analysis[END_REF][START_REF] Pavlo | A comparison of approaches to large-scale data analysis[END_REF][START_REF]Big data handbook[END_REF][START_REF] Hameed | Understanding sources of inefficiency in general-purpose chips[END_REF][START_REF] Verma | Breaking the mapreduce stage barrier[END_REF][START_REF] Tatsumi | Fast quadratic increase of multiportstorage-cell area with port number[END_REF]. The data dependency is checked by using the reordering rules presented in Section III-B.

Mutation:

We have opted out to apply mutation because of no performance improvements.

Replacement: We admit a solution into the population, if it is distinct and its fitness values is better than the worst fitness value in the population. The worst members is then discarded. This improves the average fitness value of the population gradually while maintaining genetic diversity.

Termination The algorithm terminates after observing 10 * log(n) √ a successive iterations where the minimum of the maximum parallelism of the solutions has not changed.

The algorithm 2 shows the steps of the procedure. The steps of the algorithm applies the aforementioned features of GA.

E. Simulation of Generated Schedules

Generated schedules are simulated in order to estimate the improvement in performance with calculated port and issue slot size configurations. In our experiments for this work, we have assumed that all the data resides in the cache. We have obtained the operation costs from [START_REF]Intel, Intel 64 and IA-32 Architectures Software Developer Manuals[END_REF] and [START_REF] Fog | [END_REF]. We developed a custom simulator in order to simulate reordered traces. As mentioned in Section III-A, we use PIN API [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF] for trace generation and CACTI [START_REF] Shivakumar | Cacti 3.0: An integrated cache timing, power, and area model[END_REF] for memory area estimations. We have experimented our approach with string matching algorithms that are shown in Table I. Multiport multi-issue configurations are compared to dual port single issue configuration which is taken as the baseline configuration. The algorithms are modified from [START_REF] Faro | Smart string matching algorithms research tool[END_REF].

Input
Input set contains one centimorgan DNA base pairs which is approximately one million characters of text, and ten thousand base pairs for patterns. The text alphabet size is four. Analysis, recommendation algorithms and our custom simulator have been implemented in Java and the results have been analyzed using Octave. String matching algorithms are separated into three classes based on the methods for searching strings. These classes are bit parallelism, automata, and comparison. Although, there exists different types of string matching algorithms, all of them are highly memory intensive as shown in Figure 2, thus data oriented. Control flow of string matching algorithms are similar to sparse matrix multiplication which are typical HPC applications [START_REF] Yuster | Fast sparse matrix multiplication[END_REF], [START_REF] Gustavson | Two fast algorithms for sparse matrices: Multiplication and permuted transposition[END_REF]. FSBNDMQ, FAOSO and TVSBS have different implementations. In FSBNDMQ, we change the q grams and the selected lookahead values. For example, FSBNDMQ21 means the algorithm works with 2 grams and 1 lookahead value. In FAOSO, alignment numbers vary. In TVSBS, we used different window sizes.

Our hardware setup is Intel 2.9 GHz Core i7 8GB DDR3 running 64-bit Unix OS. CACTI [START_REF] Shivakumar | Cacti 3.0: An integrated cache timing, power, and area model[END_REF] technology: 32 nm, page size: 8192 bits, burst length: 8, internal prefetch width: 8, input/output bus width: 64, ating temperature: 350 K and no selected optimizations. All benchmarks have been compiled with GCC 4.8.2 applying -O1 optimizations. We have opted for -O1 optimizations because our experiments have shown that compilation with -O2 has been equivalent to compilation with -O1. Function inlining heuristics that are mostly used in -O2 has not made any improvements. Similarly, compilation with -O3 has not been not consistent. Each time we compile with -O3, we obtain a different binary because some of heuristics are not deterministic. For reproducibility of experimental work, we did not prefer -O3. With given input set, one benchmark consumes approximately one hour of processor time.

Experiments have shown that approaches which aim to maximize parallelism by populating memory ports may not yield best memory configuration, because increasing number of port sizes impact memory area greatly as shown in Analyzed Maximum Parallelism column in Table II. Our recommendation algorithm has managed to reduce area up to 599%. Maximum parallelism extracted from SEBOM requires 22R and 1W configuration. Recommendation algorithm reduces this configuration to 3R and 1W without increasing average parallelism. This reduction in port configuration causes 599% reduction in required memory area.

There are significant differences in execution times between different types of algorithms as shown in Table II. Bit-parallel algorithms have fewer access steps than other types. More than half of the instructions of all the algorithms are consisted of memory instructions. However, there is not any relation between access steps and memory instruction profiles. FSB-NDMQ algorithm has the least average parallelism and least ratio of average memory instructions among all algorithms. FAOSO6 has the most maximum recommended parallelism and TVSBS-W8 has the most average parallelism. However, The recommended average parallelism does not seem to correlate with execution times. Recommended average parallelism value of FJS algorithm is 4.13 whereas FSBNDMQ variations have 2.85 on average. Nevertheless, FJS has three times more execution time than FSBNDMQ variations. Similarly, Recommended maximum parallelism does not convey any hint about the execution times. GRASPM has lower recommended maximum parallelism than FAOSO6, but it requires more access steps to complete. Algorithm types do not have similar analyzed maximum parallelism. Analyzed maximum parallelism of FSBNDMQ algorithm is read port dominated whereas FAOSO algorithm is dominated by write ports. Variations of the same algorithms can also have different number of analyzed maximum parallelism. TVSBS-W4 has 22 read ports whereas TVSBS-W8 has 6 read ports.

All of the algorithms have shown execution time speed up between 268% to 439 % in multi-port memory over dualport memory shown in Table II. Parallelizing only memory instructions has produced speed ups. However, the maximum speed up is obtained when both memory operations and ALU operations are parallelized. In Table II, we report the best execution times obtained after memory and ALU operations.

The types of the string matching algorithms also affect parallelism and MP area consumption. Leveraging parallelism of multi-port memory in automata based algorithms causes 1.51x increase in area over dual port memory configuration, however the speed up obtained is 387% on average. Similarly, our recommendation algorithm reduces memory area over our analysis results between 213% and 599% shown in Table II. For example, analyzed maximum parallelism of TVSBS-W4 with given input data set yields 22R, 1W configuration. Our recommendation algorithms lowers the port size to 5R, 1W configuration and this reduction decreases memory area TABLE II: Analyzed and recommended multi-port configurations, improvement in execution time with gains in area and area improvement introduced with recommendation algorithm by 526%. Furthermore, fewer port sizes do not increase the number of access steps. Thus, the average parallelism stays the same. These improvements in area and port size reduction also affect other parameters such as power consumption, energy consumption and delay positively. Nevertheless, handling multiple accesses and ALU operations increase control and arithmetic logic. Hence, aforementioned parameters can be affected negatively. We will investigate the trade-off as the future work. While leveraging ILP, we have aimed at simplicity when designing our algorithms. Because, for accurate extraction of parallelism, the input data size usually tend to be large.

Given one million string characters, one benchmark consumes two hours of processor time in given hardware setup. Recommendation algorithm consumes one hour of processor execution time. The execution time depends on the number of instructions. Execution time increases when the number of instructions increase.

V. DISCUSSION AND CONCLUSION Given a sequential algorithm, MIPT can be used for rapid exploration of parallelism. All the string matching algorithms we present are sequential. Our analysis and recommendation algorithms have leveraged parallelism and shown improvements when its inherent parallelism is exploited. This is also true with any sequential algorithm given to MIPT. Given an algorithm, MIPT can provide a starting point for migrating software to hardware for hardware co-acceleration through leveraging parallelism. After extracting parallelism, data path could be designed based on memory and core operations. Pipeline depth and units like register file or cache size could be determined. MIPT can also help to differentiate implementation differences between algorithms. For example, Table II shows recursive and iterative versions of sorting ten thousand elements with Quicksort [START_REF] Hoare | Quicksort[END_REF]. The difference between execution times and average parallelism lies in different parameters as well as the well known difference in the nature of recursion and iteration programming paradigms. Pivot point selection can change the number of accesses for both iterative and recursive version. The recursion version needs to have recursive function calls and this can be costly when number of values to sort decrease. In the iterative version, the usage of extra space for swapping values can also increase the number of memory accesses. The effects of these difference design decisions and programming choices can be identified with MIPT framework.In conclusion, we have presented MIPT framework that aims to improve ILP by analyzing execution traces and register data dependencies and recommend a new multi-port multi-issue schedule.

Figure 1 :

 1 Figure 1: MIPT process flow

Input: 1 :

 1 Execution trace list and data dependency graph Output: Reordered trace list, maximum parallelism and average parallelism metric 1 initialize reordered trace list; 2 initialize access step pointer; 3 foreach instruction in the execution trace list do 4 check reordering rules against instructions which access step pointer points to in reordered trace list; 5 if all the reordering rules are satisfied then 6 add instruction to reordered trace list at current access step; Analysis algorithm which applies the reordering rules to instructions and reorders a trace

Figure 2 :

 2 Figure 2: Memory instructions profile of string matching algorithms

:

  Analyzed reordered trace list, data dependency graph, maximum parallelism and average parallelism Output: Recommended trace list, recommended port and issue slot size 1 choose initial population; 2 evaluate each chromosome's fitness;

	3 repeat
	4	select two random chromosomes from population;
	5	apply crossover operator;
	6	foreach created new chromosome do
	7	if chromosome is a feasible reordering then
	8	evaluate chromosome's fitness;
	9	if population replacement criteria is met then
	10	admit chromosome to population pool;
	11	end
	12	end
	13	end
	14 until terminating condition is met;
		Algorithm 2: Recommendation algorithm which generates a
		recommended schedule, lowers maximum parallelism while
		preserving average parallelism
		IV. EXPERIMENTAL RESULTS

  memory area estimations use following parameters: Block size: 64 bytes, Size: 1 GB,

	Abbreviation	Algorithm	Type
	FSBNDMQ	Forward Simplified Backward Nondeterministic DAWG Matching with q-grams	bit-parallel
	BMH-SBNDM	Backward Nondeterministic DAWG Matching with Horspool Shift	bit-parallel
	KBNDM	Factorized Backward Nondeterministic DAWG Matching	bit-parallel
	FAOSO	Fast Average Optimal Shift Or	bit-parallel
	SEBOM	Simplified Extended Backward Oracle Matching	automata
	FBOM	Forward Backward Oracle Matching	automata
	SFBOM	Simplified Forward Backward Oracle Matching	automata
	TVSBS	TVSBS: A Fast Exact Pattern Matching Algorithm for Biological Sequences	comparison
	FJS	Franek Jennings Smyth String Matching	comparison
	GRASPM	Genomic Rapid Algorithm for String Pattern Matching	comparison

TABLE I :

 I String Matching Algorithms and abbreviations

ACKNOWLEDGMENT

This work has been supported by Bogazici University Scientific Research Projects (BAP) Project No: 11A01P6. We also acknowledge support of TUBITAK given to Prof. S. NIAR under Project No: 2221.