Embedded systems present stringent and often conflicting requirements. On the one side, the need for high performance within a tight energy budget favors inflexible Application Specific Integrated Circuit (ASIC) implementations; on the other side, a short time-to-market demands programmability. Hybrid architectures such as special-purpose customized processors represent an attractive solution, as they are programmable by software, but use dedicated hardware to accelerate parts of the computation. In such a scenario, the capability of automatically identifying the computation parts to be realized in hardware is highly desirable, in order to reduce design time and effort. This paper aims at advancing the state-of-the-art in this field. We recognize that subgraphs of control flow graphs having a single input control point and a single output control point, that we call regions, are good targets for the synthesis of application specific hardware accelerators. We therefore provide a method to identify them and an LLVM-based toolchain (named RegionSeeker) that, analyzing a software application, automatically selects its most profitable regions given an area constraint. Experimental evidence shows that the accelerators identified by RegionSeeker provide a speedup of up to $4.6\boldsymbol {\times }$ and, on average, approximately 30% higher speedup is achieved compared to state-of-the-art identification techniques.

Summary More than 120 algorithms have been developed for exact string matching within the last 40 years. We show by experiments that the naïve algorithm exploiting SIMD instructions of modern CPUs (with symbols compared in a special order) is the fastest one for patterns of length up to about 50 symbols and extremely good for longer patterns and small alphabets. The algorithm compares 16 or 32 characters in parallel by applying SSE2 or AVX2 instructions, respectively. Moreover, it uses loop peeling to further speed up the searching phase. We tried several orders for comparisons of pattern symbols, and the increasing order of their probabilities in the text was the best.

The longest common substring with k-mismatches problem is to find, given two strings S1 and S2, a longest substring A1 of S1 and A2 of S2 such that the Hamming distance between A1 and A2 is ≤k. We introduce a practical O(nm) time and O(1) space solution for this problem, where n and m are the lengths of S1 and S2, respectively. This algorithm can also be used to compute the matching statistics with k-mismatches of S1 and S2 in O(nm) time and O(m) space. Moreover, we also present a theoretical solution for the k=1 case which runs in O(nlog⁡m) time, assuming m≤n, and uses O(m) space, improving over the existing O(nm) time and O(m) space bound of Babenko and Starikovskaya [1].

Automatic identification of custom instructions (CI) is the process of supporting the programmer in choosing automatically beneficial parts of the application source code that can then be synthesized and run on dedicated hardware. Identification is typically modeled as choosing a subgraph from a graph, representing the application, that has the highest speedup potential when implemented in custom hardware, and that fulfills the constraints of convexity and of a given maximum number of inputs and outputs. Existing algorithms for CI identification either enumerate all the valid subgraphs under the constraints of convexity and I/O, or return the subset of all maximal valid subgraphs with respect to convexity only. The downside of the former approach is that enumerating all valid subgraphs is costly, especially for large values of input and output constraints, while we may be interested in the subgraphs which obtain the best speedup only. Instead, the latter approach may fail to find a feasible solution, since the valid subgraphs with respect to convexity only can be too large to be useful. In this paper, we present a novel approach which attempts to fill the gap between the existing methods. In particular, we present an algorithm that enumerates the subset of all maximum valid subgraphs with respect to convexity and number of inputs and outputs. Our method revisits and combines the existing approaches and yields an algorithm which is effective and outperforms the state-of-the-art for large values of input and output constraints.