Jane Street-ի ASIC-ի հակադարձ ինժեներիայի խնդիրը՝ լուծված մեկ ամսում

Jane Street-ի հրապարակային մարտահրավերները հայտնի են նրանով, որ ինժեներներին տանում են երկար շրջադարձերի մեջ։ Դրանցից մեկը՝ «Can you reverse engineer an ASIC?» ապարատային խնդիրը, Jestoph կեղծանվամբ բլոգ վարող ծրագրավորող Քրիսին զբաղեցրել է մոտ մեկ ամիս. սեպտեմբերի 4-ին նա հրապարակել է լուծման մանրամասն նկարագրությունը։

Ինչ էր պահանջում խնդիրը

Խնդիրն այն է, որ վերցնելով GDS ֆայլը՝ սիլիկոնի դասավորության նկարագրությունը, հակառակ ուղղությամբ պետք է պարզել, թե ինչ է անում սխեման։ ASIC-ը (application-specific integrated circuit) չիպ է, որը նախատեսված է մեկ նեղ խնդրի, այլ ոչ թե ընդհանուր հաշվարկների համար։ Մարտահրավերը բաղկացած էր երկու մասից՝ տաքացման փուլից, որտեղ տրված էր չիպի իրական նախագիծը, և հիմնական խնդրից, որը, հեղինակի խոսքով, ուղեկցվում էր միայն «ամուր ձեռքսեղմումով և հաջողության մաղթանքով»։

Դասավորությունից՝ աշխատող սիմուլյացիա

Առաջին հուշումը խնդրին կցված VCD ֆայլն էր։ Փոքրիկ C ծրագրով այն կարդալով ստացվեց «TRY AGAIN» հաղորդագրությունը, այսինքն՝ սխեման տեքստ է փոխանցում։ Այնուհետև նա օգտագործել է Python-ի gdstk գրադարանը դասավորության ֆայլերը բացելու համար, թեև հետագայում գրել է սեփական սխեմաների սիմուլյատոր, ապարատային նկարագրության լեզվի վերլուծիչ և թեստային միջավայր. այս շեղումները նա այժմ գնահատում է որպես հիմնականում վատնված ժամանակ։ Տաքացման փուլում կար 27 տարր, իսկ իրական խնդրում՝ 81 տեսակի մոտ 10 000 բաղադրիչ (տաքացման փուլում՝ շուրջ 20 տեսակ). զտումից հետո մնացել է շուրջ 1000 լարային ուղի և 17 000 պոլիգոն։

Սխալ հենց խնդրի մեջ

Սիմուլյացիան բացահայտել է չկառավարվող լար, որը միացած էր միայն երկու մուտքային փին, որի կողքին էլ կար փին, որը ոչ մուտք էր, ոչ ելք։ Նա այդ մասին տեղեկացրել է Jane Street-ին և հաջորդ օրը ստացել հաստատում, որ ճիշտ է, թեև այդ թերությունը չի ազդում խնդրի արդյունքի վրա։ Այդ սխալի մասին հաղորդագրությունն ինքը համարում է իր ամենահետաքրքիր տեխնիկական ձեռքբերումներից մեկը։

Լուծում հակառակ ուղղությամբ՝ սահմանափակումների լուծիչով

120 բիթանոց մուտքը ամբողջությամբ ստուգելը իրատեսական չէր, ուստի նա նախագիծը գործարկել է ժամանակի ընթացքում հակառակ ուղղությամբ՝ ցանկալի ազդանշանները ներկայացնելով որպես սահմանափակումներ z3 լուծիչի համար։ Միաժամանակ բարձր պետք է լինեին շուրջ 24 լարեր. 22-ը նա ստացել է առանձին, իսկ մնացածը լուծվել են, երբ նկատել է, որ տարրերի մուտքերի մեծ մասին անհրաժեշտ է ընդամենը երկու իմպուլս՝ 11-ի բազմապատիկ ընդմիջումներով։ Ամբողջական սիմուլյացիան տվել է հաղթող արդյունքը՝ «(* TWO STARS *)»։ Սխեման նաև պատասխանում է «EMPTY SKY» զրոներով մուտքին և «BIG BANG»՝ միավորներով լցված մուտքին։ Հեղինակը նշում է, որ Jane Street-ը ակնարկել է առաջիկա ամիսներին նոր մարտահրավերի մասին։