Felicia IONESCU, Mihai IONESCU, Elena-Cristina COCONU, George-Valentin STOICA On the Granularity and Load-Balancing of Parallel Test Vectors Generation Abstract. The paper studies parallel implementation of automatic test vectors generation on multiprocessor systems using Boolean Difference Algorithm (BDA). Different granularities of parallel implementation of BDA can be obtained depending on which loop of the algorithm is distributed over concurrent processes (threads). The analysis of the algorithm points out different types of data-dependencies that require different techniques for removing them: circuit model replication, mutual exclusion mechanisms (serialization) and synchronization points (barriers). Toward load-balancing of the work among processors, static and dynamic partitioning of computational tasks for each grain level of parallel implementation is studied. For each parallelization strategy, the theoretical overhead and speedup is estimated, in order to select the most efficient solution. This estimation reveals that decreasing of the granularity, from coarse-grain to fine-grain, reduces the load-imbalance overhead and increases serialization overhead and synchronization barriers overhead. In practical cases, in which the number of processors of the multiprocessor system is quite small (maximum 128 processors), and combinational circuits are large, with thousands of gates and input vectors, dynamic partitioning of faults produces the maximum speedup and efficiency.