Paralelizando um algoritmo de backtracking no navegador com Web Workers e WebAssembly
Resumo
O uso de navegadores modernos se mostra cada vez mais essencial na atualidade. Recursos como Web Workers vêm se tornando mais adotados nos mais usados navegadores da Internet, possibilitando melhoria de desempenho em aplicações web, e por consequência, execução de tarefas de maior demanda computacional dentro desses mesmos navegadores. Este artigo explora uma técnica de paralelismo de tarefas usando Web Workers, apresentando como estudo de caso um algoritmo de geração de palavras cruzadas, executando-os em um navegador. Os resultados mostram, até mesmo, speedups superlineares para a versão paralela do algoritmo estudado.
Palavras-chave:
Algoritmos Paralelos e Distribuídos, Modelos de Programação, Técnicas e Métodos de Extração de Paralelismo
Referências
Abelson, H., Sussman, G. J., and Sussman, J. (1996). Structure and Interpretation of Computer Programs. MIT Press, 2nd edition.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman & Co.
Halic, C. P. S. (2019). Estudo do processo de compilação para webassembly.
Herman, D., Wagner, L., and Zakai, A. (2014). asm.js, http://asmjs.org/spec/latest/.
Herrera, D., Chen, H., Lavoie, E., and Hendren, L. (2018). Webassembly and javascript challenge: Numerical program performance using modern browser technologies and devices. Technical report, University of McGill.
Mozilla (2021). Web workers api, https://developer.mozilla.org/en-us/docs/web/api/web_workers_api.
Rao, V. N. and Kumar, V. (1987). Parallel depth first search. part i. implementation. International Journal of Parallel Programming, 16:479-499.
Rauschmayer, A. (2015). Webassembly: a binary format for the web, https://2ality.com/2015/06/web-assembly.html.
Stats, I. W. (2021). Internet usage statistics, https://internetworldstats.com/stats.htm.
W3C (2021). Web workers. Technical report, World Wide Web Consortium.
Wagner, L. (2013). asm.js in firefox nightly, https://blog.mozilla.org/luke/2013/03/21/asm-js-in-firefox-nightly/.
WCG (2019). Webassembly roadmap, https://webassembly.org/roadmap/.
WHATWG (2021a). Dom living standard, https://dom.spec.whatwg.org/.
WHATWG (2021b). Html living standard, https://html.spec.whatwg.org/.
Garey, M. R. and Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman & Co.
Halic, C. P. S. (2019). Estudo do processo de compilação para webassembly.
Herman, D., Wagner, L., and Zakai, A. (2014). asm.js, http://asmjs.org/spec/latest/.
Herrera, D., Chen, H., Lavoie, E., and Hendren, L. (2018). Webassembly and javascript challenge: Numerical program performance using modern browser technologies and devices. Technical report, University of McGill.
Mozilla (2021). Web workers api, https://developer.mozilla.org/en-us/docs/web/api/web_workers_api.
Rao, V. N. and Kumar, V. (1987). Parallel depth first search. part i. implementation. International Journal of Parallel Programming, 16:479-499.
Rauschmayer, A. (2015). Webassembly: a binary format for the web, https://2ality.com/2015/06/web-assembly.html.
Stats, I. W. (2021). Internet usage statistics, https://internetworldstats.com/stats.htm.
W3C (2021). Web workers. Technical report, World Wide Web Consortium.
Wagner, L. (2013). asm.js in firefox nightly, https://blog.mozilla.org/luke/2013/03/21/asm-js-in-firefox-nightly/.
WCG (2019). Webassembly roadmap, https://webassembly.org/roadmap/.
WHATWG (2021a). Dom living standard, https://dom.spec.whatwg.org/.
WHATWG (2021b). Html living standard, https://html.spec.whatwg.org/.
Publicado
07/04/2022
Como Citar
RODRIGUES, Daniel T.; BIANCHINI, Calebe de Paula.
Paralelizando um algoritmo de backtracking no navegador com Web Workers e WebAssembly. In: ESCOLA REGIONAL DE ALTO DESEMPENHO DE SÃO PAULO (ERAD-SP), 13. , 2022, Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 5-8.
DOI: https://doi.org/10.5753/eradsp.2022.221984.
