Finita stat maskiner (FSM) är ryggraden i många tillämpningar, men är svåra att parallellisera på grund av deras inneboende beroenden. Spekulativ FSM parallellisering har visat löfte på flerkärniga maskiner med upp till åtta kärnor. Men i takt med att hårdvaruparallalismen växer (t.ex. har Xeon Phi upp till 288 logiska kärnor) uppstår en grundläggande fråga: Hur ökar den spekulativa FSM-parallaliseringen i takt med att antalet kärnor ökar? Utan att besvara denna fråga, befintliga metoder för spekulativ FSM parallellisering helt enkelt välja att använda alla tillgängliga kärnor, som kanske inte bara slösa datorresurser, men också resultera i suboptimal prestanda. I detta arbete genomför vi en systematisk skalbarhetsanalys för spekulativ FSM parallellisering. Till skillnad från många andra parallelliseringar som kan modelleras av den klassiska Amdahls lag eller dess enkla förlängningar, spekulativa FSM-parallellationsskalor okonventionellt på grund av den icke-deterministiska karaktären av spekulation och kostnadsvariationer av misspekulation. För att möta dessa utmaningar introducerar detta arbete ett spektrum av skalbarhetsmodeller som är anpassade till egenskaperna hos specifika FSM och den underliggande arkitekturen. Modellerna, för första gången, exakt fånga skalbarheten av spekulativ parallellisering för olika FSM beräkningar, och tydligt visa förekomsten av en "söt plats" i termer av antalet kärnor som används av spekulativ FSM parallellisering för att uppnå optimal prestanda. För att göra skalbarhetsmodellerna praktiska utvecklar vi S3, en skalbarhetskänslig spekulationsram för FSM-parallalisering. För varje givet FSM kan S3 automatiskt karakterisera sina egenskaper och analysera sin skalbarhet, och därmed vägleda spekulativ parallellisering mot optimal prestanda och effektivare användning av datorresurser. Utvärderingar av olika FSM och arkitekturer bekräftar att de föreslagna modellerna är korrekta och visar att S3 uppnår en betydande hastighetsökning (upp till 5X) och energibesparingar (upp till 77 %).
Qiu m.fl. REF konstaterade att spekulativ FSM-parallalisering inte är skalbar med ett ökande antal kärnor.
Enabling scalability-sensitive speculative parallelization for FSM computations
{'venue': "ICS '17", 'journal': None, 'mag_field_of_study': ['Computer Science']}