{'fraction_non_alphanumeric': 0.01927710843373494, 'fraction_numerical': 0.0024096385542168677, 'mean_word_length': 5.701612903225806, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
OPTIMAL ALGORITHMS FOR SUBSTRATE TESTING IN MULTI-CHIP MODULES

Multi-chip module (MCM) packaging techniques present several new technical challenges, notably substrate testing. We formulate MCM substrate testing as a problem of connectivity verification in trees via k-probes, and present a linear-time algorithm which computes a minimum set of probes achieving complete open fault coverage. Since actual substrate testing also involves scheduling probe operations, we formulate efficient probe scheduling as a special type of metric traveling salesman optimization and give a provably-good heuristic. Empirical results using both random and industry benchmarks demonstrate reductions in testing costs of up to 21% over previous methods. We conclude with generalizations to alternate probe technologies and several open problems.