пїњ

ѕ–ќ¬≈–яёў»≈ “≈—“џ CROSSTALK Ќ≈»—ѕ–ј¬Ќќ—“≈… Ќј ќ—Ќќ¬≈ Ё¬ќЋё÷»ќЌЌџ’ ћ≈“ќƒќ¬

”ƒ  681.32
ё.ј. — ќЅ÷ќ¬, д-р техн. наук, проф., зав. каф. ј—” ƒонЌ“”
(г. ƒонецк),
¬.ё. — ќЅ÷ќ¬, канд. техн. наук, доц. каф. ј—” ƒонЌ“” (г. ƒонецк),
Ќј——≈– 1яƒ  .ћ., аспирант каф. ј—” ƒонЌ“” (г. ƒонецк)
ѕ–ќ¬≈–яёў»≈ “≈—“џ CROSSTALK Ќ≈»—ѕ–ј¬Ќќ—“≈… Ќј
ќ—Ќќ¬≈ Ё¬ќЋё÷»ќЌЌџ’ ћ≈“ќƒќ¬
–ассматриваетс€ проблема построени€ провер€ющих тестов дл€ "перекрестных неисправностей" типа Crosstalk, характерных дл€ глубокого субмикронного проектировани€ элементной базы современных компьютерных систем. ѕри решении поставленной задачи используетс€ многозначное логическое моделирование и генетический алгоритм генерации провер€ющих тестов дл€ этих неисправностей. »л.:1. Ѕиблиогр.: 15 назв.
 лючевые слова: crosstalk неисправности, провер€ющие тесты, генетический алгоритм, многозначное логическое моделирование.
јктуальность. —овременные технологии производства цифровых систем и их элементной базы требуют анализа не только константных, но и более адекватных неисправностей. ¬ насто€щее врем€ используютс€ более сложные модели неисправностей, таких как замыкани€, "транзистор посто€нно открыт", "транзистор посто€нно закрыт", задержки распространени€ сигналов, наводки и т.п. [1].
¬следствие технологического прогресса, который ведет к увеличению плотности элементов на кристалле, росту числа пересечений провод€щих слоев и повышению рабочей частоты, тестировани€ классических константных неисправностей в насто€щее врем€ €вно недостаточно, поскольку необходимо анализировать физические дефекты, которые вли€ют на временные характеристики схемы. ќсобенно это характерно дл€ глубокого субмикронного (deep submicron - DSM) проектировани€. ”величение числа транзисторов на кристалле ведет к тому, что большее количество элементов переключаютс€ одновременно, что может уменьшить дл€ них уровень напр€жени€ и увеличить задержки распространени€ сигналов. ѕри этом некоторые пересекающиес€ линии, которые предполагались электрически изолированными, могут взаимодействовать друг с другом. ќдно из подобных взаимодействий, вызванное паразитической емкостной св€зью между проводниками, называетс€ "crosstalk" (перекрестна€ помеха), может привести к функциональным проблемам и ухудшить временные характеристики.
ќбычно рассматриваютс€ два основных типа перекрестных помех: 1) "crosstalk" индуцированные импульсы; 2) "crosstalk" индуцированные задержки. ¬ первом случае быстро переключающа€с€ лини€ - "агрессор" (aggressor) может индуцировать короткий импульс на статической линии -"жертве" (victim). ¬ зависимости от амплитуды и ширины эти импульсы могут оказывать существенное вли€ние на характеристики схемы.
¬торой случай (индуцированные задержки) имеет место тогда, когда на лини€х "агрессоре" и "жертве" происход€т (почти) одновременные переходы сигналов. ≈сли на обеих лини€х переходы в одном направлении, то врем€ перехода сокращаетс€ и, следовательно, уменьшаетс€ врем€ задержки распространени€ сигналов. Ётот эффект называетс€ "перекрестным ускорением" ("crosstalk speedup"). —ильный "агрессор" может вызвать задержку распространени€ сигнала на линии-"жертве", котора€ имеет противоположное значение сигнала. ≈сли на лини€х "агрессоре" и "жертве" происход€т переходы сигналов в противоположных направлени€х, то врем€ перехода увеличиваетс€ и имеет место эффект "перекрестного замедлени€" ("crosstalk slowdown"). ≈сли вызванный шум на линии-"жертве" больше порогового напр€жени€ или индуцированна€ задержка больше допустимой, то это может привести к логическим отказам или функциональным проблемам на соседних триггерах или выходах.
ѕерекрестные неисправности вызываютс€ паразитическими наводками между соседними провод€щими лини€ми, которые в общем случае имеют индуктивные и емкостные составл€ющие.  ак правило, такие св€зи имеют малые значени€ индуктивности. Ќо в отдельных случа€х, например, на высоких частотах дл€ линий, непосредственно св€занных с питанием или землей, которые имеют достаточно большую длину и ширину (сопротивление R соизмеримо с raL), вли€ние индуктивной св€ти значительно и может порождать существенные токи. Ќо дл€ информационных линий в схемах доминируют емкостные св€ти.
јнализ литературы. –аботы по моделированию и тестированию неисправностей типа "crosstalk" ведутс€ с середины 90-х годов. “ак в [2] предложен метод, который основан на поиске пары входных наборов, которые устанавливают определенное значение сигнала на линии-"жертве" и вызывают переход на линии-"агрессоре", который обеспечивает распространение вли€ни€ неисправности до одного из внешних выходов. ¬ этой работе рассматриваютс€ "crosstalk" индуцированные импульсы.
јвторы [3 - 5] разработали смешанный генератор тестовых сигналов XGEN дл€ "crosstalk" индуцированных задержек. ќни предложили смешанный метод генерации тестов, где при поиске двоичных наборов используетс€ аналоговое моделирование, которое позвол€ет оценить задержки распространени€ сигналов. »спользу€ преобразование Ћапласа они получили выражени€ дл€ неисправностей "crosstalk" в 5-области, которые используютс€ дл€ анализа зависимости атрибутов импульса в схеме с сосредоточенными параметрами и временных характеристик фронтов. —татический временной анализ позвол€ет определить временные окна дл€ входов и выходов элементов. »скомое временное окно находитс€ в результате пересечени€ временных окон "агрессора" и "жертвы". ƒл€ заданной неисправности -определенной пары "агрессор-жертва" метод позвол€ет установить необходимые значени€ на взаимодействующих лини€х и распространить
вли€ние неисправности до внешнего выхода. ѕри генерации тестов используетс€ 11-значный алфавит и модификаци€ метода PODEM на этапе доопределени€ (justification). –азработанный алгоритм не гарантирует построение тестов вследствие ограничений дл€ условий распространени€ эффектов неисправностей и используемой (11-значной) логической системы.
¬ [6] авторы развили модель задержки пути в комбинации с критическим путем и множеством источников взаимодействующих с этим путем. «десь в качестве основы используетс€ метод генерации тестов дл€ неисправностей типа "задержка распространени€ сигнала" без фазы доопределени€ (justification). ј на этапе доопределени€ (justification) примен€етс€ генетический алгоритм, который в процессе построени€ теста использует временные характеристики. ƒалее это направление получило развитие в [7], где предложено решение задачи построени€ тестов в случае многих "агрессоров", воздействующих да определенный путь. «десь строитс€ граф импликации, который учитывает логическую и структурную информацию схемы дл€ проверки конфликтных ситуаций в процессе генерации тестов. ѕри поиске тестовых наборов используетс€ модификаци€ метода PODEM.
–абота [8] посв€щена тестированию неисправностей "crosstalk" -индуцированных задержек. јлгоритм построени€ тестов основан на генерации критических путей на основе статического временного анализа схемы.  ритерий устойчивой тестируемости используетс€ при проверке чувствительности путей. ƒл€ чувствительного пути активируютс€ пары "агрессор-жертва" таким образом, чтобы максимизировать воздействие агрессора на путь и вызвать задержку распространени€ сигнала по этому пути.
¬ [9] предложен генератор тестов на основе единичной точной модели задержки. «десь активизируетс€ подпуть дл€ выполнени€ условий переходов сигналов. »звестна€ модель неисправности типа "задержка" модифицируетс€ дл€ тестировани€ индуцированных задержек. ƒл€ сокращени€ множества анализируемых неисправностей выполн€етс€ препроцессорна€ обработка дл€ критических путей.
јвторы [10] разработали метод генерации тестов на основе PODEM. ƒл€ тестировани€ "crosstalk" необходимо подать на внешние входы необходимые переходы и обеспечить распространение вли€ни€ неисправности на внешний выход.  ажда€ из этих задач формулируетс€ отдельно, а конечное решение получаетс€ в результате пересечени€ решений указанных подзадач.
¬ [11] при генерации тестов дл€ "crosstalk" - индуцированных задержек используетс€ алгоритм построени€ тестов дл€ неисправностей типа "задержка", основанный на троичном алфавите, где неопределенное значение примен€етс€ дл€ моделировани€ переходов сигналов, которые вызываютс€ перекрестными неисправност€ми.
¬ работе [12] при решении задачи построени€ тестов дл€ "crosstalk" примен€етс€ 0-1 целочисленное программирование на основе традиционных методов генерации тестов дл€ константных неисправностей. ћаксимальна€
активаци€ агрессора формулируетс€ в терминах линейного программировани€, а распространение вли€ни€ неисправности решаетс€ традиционными средствами.
—ледует отметить, что все вышеперечисленные работы при генерации тестов используют механизмы "возврата назад" по схеме, которые требуют значительных вычислительных ресурсов.
— другой стороны, существует группа методов, которые основаны на моделировании и не требуют "возврата назад".   ним относитс€, например, работа [13], где моделирование примен€етс€ дл€ тестировани€ перекрестных неисправностей. «десь используетс€ алгоритм редакции дл€ неисправностей-кандидатов, что позвол€ет получать компактное множество целевых неисправностей за счет исключени€ тех неисправностей, которые никогда не могут быть активированы и обнаружены. ѕри этом используетс€ последовательный симул€тор дл€ моделировани€ задержек путей.  роме этого, используетс€ аналогова€ макромодель дл€ вычислени€ задержек сигналов вследствие перекрестного взаимодействи€. «десь с каждой неисправностью ассоциируетс€ одна пара агрессор-жертва. ¬ходные наборы в процессе поиска генерируютс€ случайным образом.
јвторы [14] предложили симул€тор неисправностей, который включает одну линию-жертву и множество линий-агрессоров. ѕри генерации тестов используетс€ двоичное логическое моделирование и в качестве основы используютс€ тесты дл€ константных неисправностей. —ледует отметить, что методы, основанные на моделировании, требуют хороших эвристик дл€ генерации входных наборов и получаемые тестовые последовательности, как правило, имеют большую длину.
ѕостановка проблемы. ѕри построении провер€ющего теста дл€ такой неисправности необходимо: 1) найти входные наборы, которые вызывают необходимый переход сигналов на линии-агрессоре: 2) найти входные наборы, обеспечивающие необходимый статический сигнал и линии-"жертве" и распространение возникшего импульса от жертвы до одного из внешних выходов. ѕусть состо€ни€ линии-жертвы g и линии-агрессора к описываютс€ двум€ булевыми функци€ми от переменных, св€занных с внешними входами, g(x1, х2,... , хп) и к(х1, х2,... , хп). јналогично на каждом внешнем выходе реализуетс€ булева функци€ /](х1, х2,... ,хп, g, к), котора€ зависит как от внешних переменных (х1, х2,... , хп), так и от внутренних переменных g, к. ќтметим, что переменные внешних входов при тестировании рассматриваемой неисправности могут принимать только четыре значени€ "статический 0" (0 ^ 0), "статическа€ 1" (1 ^ 1), передний фронт ЅТ (0 ^ 1) и задний
фронт Ѕ (1 ^ 0).
ƒл€ проверки перекрестной неисправности с положительным импульсом необходимы такие значени€ внешних входов, которые обеспечивают на линии-агрессоре передний фронт ЅТ (0 ^ 1), а на линии-жертве "статический
0" (0 ^ 0). “огда проблема построени€ теста дл€ данной перекрестной неисправности сводитс€ к поиску таких пар входных наборов, которые обеспечивают: (1) значение 0 на линии-жертве, (2) - значение ЅТ на линии-агрессоре и (3) обеспечивает распространение вли€ни€ неисправности от линии-жертвы до одного из внешних входов.
јналогично дл€ проверки перекрестной неисправности положительным импульсом необходимы такие значени€ внешних входов, которые обеспечивают на линии-агрессоре задний фронт Ѕ (1 ^ 0), а на линии-жертве
"статическа€ 1" (1 ^ 1). –ассмотрим комбинационную схему рис., где g и к -внутренние линии, из которых к €вл€етс€ "агрессором" (воздействующей линией) и g - "жертвой". ѕри построении провер€ющего теста дл€ такой неисправности необходимо: 1) найти входные наборы, которые вызывают необходимый переход сигналов на линии-агрессоре: 2) найти входные наборы, обеспечивающие необходимый статический сигнал на линии-"жертве" и распространение возникшего импульса от жертвы до одного из внешних входов, как показано на рис.
–ис. Ќеисправность "crosstalk" - перекрестна€ помеха.
√енетический алгоритм. ќчевидно, что провер€ющий тест дл€ перекрестных неисправностей должен состо€ть из пар наборов, обеспечивающих приведенные выше услови€. ѕри поиске пар тестовых наборов можно использовать генетический алгоритм и многозначный алфавит [1]. ѕри этом генетический алгоритм обеспечивает механизм направленного случайного поиска пар тестовых наборов, удовлетвор€ющих указанным услови€м. Ќа наш взгл€д применение эволюционных методов при построении провер€ющих тестов дл€ таких неисправностей еще более оправдано, чем дл€ классических константных неисправностей. ћожно провести аналогию с решением задач численной оптимизации, где √ј целесообразно использовать,
прежде всего, там, где не работают классические градиентные методы. —ледует отметить, что √ј часто позвол€ют задачу синтеза, в каком то смысле, свести к задаче анализа. ≈сли есть средства анализа (моделировани€ поведени€ исправной или неисправной цифровой системы), то √ј обеспечивают целенаправленный случайный поиск решени€ задачи синтеза. ѕри этом задачи синтеза и анализа могут выполн€тьс€ на различных уровн€х. Ќапример, задача синтеза тестов может решатьс€ на логическом уровне с использованием логической модели схемы, а задача анализа - на переключательном уровне (или с использованием модели электрических схем). Ёто позвол€ет строить тесты дл€ новых типов неисправностей (практически дл€ произвольных неисправностей, дл€ которых есть соответствующа€ модель).
ƒл€ того, что использовать √ј при решении кокретной задачи прежде всего необходимо определить пон€тие особи, попул€ции, генетических операторов кроссинговера и мутации, фитнесс-функцию, котора€ позвол€ет оценивать качество потенциального решени€. ќчевидно, что в качестве особи здесь целесообразно использовать пару входных наборов, множество которых составл€ет попул€цию. ѕоскольку пара наборов представл€етс€ двоичной строкой, то можно использовать стандартные операторы кроссинговера и мутации [2], среди которых мы отдаем предпочтение однородному кроссинговеру. ƒл€ оценки значени€ фитнесс-функции мы используем данные логического моделировани€ в многозначном алфавите [1], с помощью которого определ€ютс€ новые неисправности, которые провер€ютс€ исследуемой парой входных наборов (потенциальным решением).
¬ыводы. Ёксперименты дл€ комбинационных цифровых схем показали, что применение √ј позвол€ет эффективно решать задачу построени€ тестов дл€ "crosstalk" неисправаностей и дают высокую полноту обнаружени€. Ќа следующем этапе будет решатьс€ задача построени€ тестов дл€ этих неисправностей дл€ схем с пам€тью.
—писок литературы: 1. —кобцов ё.ј. Ћогическое моделирование и тестирование цифровых устройств / ё.ј. —кобцов, ¬.ё. —кобцов. - ƒонецк: »ѕћћ ЌјЌ”, ƒонЌ“”, 2005. - 436 с. 2. Rubio. An approach to the analysis and detection of crosstalk faults in digital VLSI circuits / Rubio, N. Itazaki, X. Xu, K. Kinoshita // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. - 1994. - Vol. 13. - є. 3. - –. 387-394. 3. Chen W.Y. Analytic Models for Crosstalk Delay and Pulse Analysis under Non-Ideal Inputs / W.Y. Chen, S.K. Gupta, M.A. Breuer // Proc.of the IntТl.Test Conf. - 1997. - –. 809-818. 4. Chen W.Y. Test generation for Cross-Induced Delay in Integrated Citcuits / W.Y. Chen, S.K. Gupta, M.A. Breuer // Proceedings of IEEE International Test Conference. - 1999. -–. 191-200. 5. Chen W.Y. Test generation for Cross-Induced Faults: Framework and computational results / W.Y. Chen, S.K. Gupta, M.A. Breuer // Journal of Electronic Testing: Theory and Applications. -2002. - Vol. 16. - P. 17-28. 6. Krstic A. Delay Testing Considering Cross-Induced Effects / J. Krstic, J. Liou, Y.-M. Jiang, K.-T. Cheng // Proceedings of International Conference. - 2001. 7. Bai X. A Hybrid Structural SAT Based ATPG for Crosstalk / X. Bai, S. Dey, A. Krstic // Proceedings of International Conference. - 2003. - P. 112-121. 8. Arunachalam A. A Novel Algorithm for Testing Crosstalk Induced Delay Faults in VLSI Cicuits / Aniket and R. Arunachalam // Proceedings of International Conference on VLSI Design. - 2005. - P. 479-484. 9. Li H. Selection of Crosstalk-induced Faults in Enhanced Delay test / H. Li, X. Li // Journal of Electronic Testing: Theory and Applications. - 2005. - Vol. 21. - є 2. -
–. 181-195. 10. Palit A.K. Test Pattern Generation for Crosstalk Faults in DSM chips using Mofified PODEM / A.K. Palit, K.K. Duganapali, W.-TuZ Anheier. - –. 41^45. 11. Sunghoon Chun. XPDF-ATPG: An Efficient Test Pattern Generation for Crosstalk-Induced Faults / Chun Sunghoon, Kim Yongjoon, Yang Myuang-Hoon, Kang Sungho // 17th Asian Test Symposium. - 2008. - –. 83-88. 12. Kunal P. Ganeshpure. On ATPG for Multiple Aggressor Crosstalk Faults in Presence of Gate Delays / P. Ganeshpure Kunal, Kundu Sandir // Proceedings of IEEE International Test Conference. - 2007. -–. 1-7. 13. Chary Shweta. Automatic path delay test generation for combined Resistive Vias Resistive bridges and Capacitive Crosstalk delay faults / Shweta Chary, L. Bushnell Michael // Proceedings of the 19th International conference on VLSI Design. - 2006. - –. 413Ч418. 14. Phadoongsidhi Marong. SCINDY: Logic Crosstalk Delay Fault Simulation in Sequential Circuits / Marong Phadoongsidhi, K. Saluja Kewal // 18th Internartional Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID,05). - 2005. - –. 820-823. 15. —кобцов ё.ј. ќсновы эволюционных вычислений / ё.ј. —кобцов. Ч ƒонецк: ƒонЌ“”, 2008. - 326 с.
”ƒ  681.32
ѕерев≥р€льн≥ тести crosstalk несправностей на основ≥ еволюц≥йних метод≥в / —кобцов ё.ќ., —кобцов ¬.ё., Ќассер ≤€д  .ћ. // ¬≥сник Ќ“” "’ѕ≤". “ематичний випуск: ≤нформатика ≥ моделюванн€. - ’арк≥в: Ќ“” "’ѕ≤". - 2010. - є 31. - —. 170 - 176.
–озгл€даЇтьс€ проблема побудови перев≥р€льник тест≥в дл€ "перехресних несправностей" типу crosstalk, характерних дл€ глибокого субм≥кронного проектуванн€ елементноњ бази сучасних комп'ютерних систем. ѕри розв'€зку поставленого завданн€ використовуЇтьс€ багатозначне лог≥чне моделюванн€ й генетичний алгоритм генерац≥њ тест≥в, що перев≥р€ють, дл€ цих несправностей. ≤л.: 1. Ѕ≥бл≥огр.: 15 назв.
 лючов≥ слова: crosstalk несправност≥, перев≥р€льн≥ тести, генетичний алгоритм,
багатозначне лог≥чне моделюванн€.
UDC 681.32
Checking tests for crosstalk faults on the basis evolutionary methods/ Skobtsov Y.A., Skobtsov V.Y., Nasser Iyad K.M. // Herald of the National Technical University "KhPI". Subject issue: Information Science and Modelling. - Kharkov: NTU "KhPI". - 2010. - є. 31. - P. 170 - 176.
The problem of construction of checking tests is examined for the crosstalk faults, which are characteristic for the deep submicrometer design of element base for the modern computer systems. For a decision the set problem the multiple-valued logical simulation and genetic algorithm of generation of checking tests are used for these faults. Figs: 1. Refs: 15 titles.
Key words: crosstalk faults, checking tests, genetic algorithm, multivalued logic simulation.
ѕоступила в редакцию 29.05.2010

пїњ