O filósofo alemão Fredrich Nietzsche disse certa vez que “os fios invisíveis são os laços mais fortes”. Poderíamos pensar em “fios invisíveis” como ligando objetos relacionados, como as casas na rota de um motorista de entrega, ou entidades mais nebulosas, como transações numa rede financeira ou utilizadores numa rede social.
O cientista da computação Julian Shun estuda esses tipos de conexões multifacetadas, mas muitas vezes invisíveis, usando gráficos, onde os objetos são representados como pontos, ou vértices, e as relações entre eles são modeladas por segmentos de linha, ou arestas.
Shun, professor associado recém-admitido no Departamento de Engenharia Elétrica e Ciência da Computação, projeta algoritmos gráficos que podem ser usados para encontrar o caminho mais curto entre as casas na rota do motorista de entrega ou detectar transações fraudulentas feitas por atores mal-intencionados em uma rede financeira.
Mas com o quantity crescente de dados, essas redes cresceram e incluem milhares de milhões ou mesmo biliões de objetos e ligações. Para encontrar soluções eficientes, Shun cria algoritmos de alto desempenho que aproveitam a computação paralela para analisar rapidamente até mesmo os gráficos mais enormes. Como a programação paralela é notoriamente difícil, ele também desenvolve estruturas de programação fáceis de usar que tornam mais fácil para outros escreverem seus próprios algoritmos gráficos eficientes.
“Se você está pesquisando algo em um mecanismo de busca ou rede social, deseja obter seus resultados muito rapidamente. Se você está tentando identificar transações financeiras fraudulentas em um banco, deseja fazê-lo em tempo actual para minimizar os danos. Algoritmos paralelos podem acelerar as coisas usando mais recursos computacionais”, explica Shun, que também é pesquisador principal do Laboratório de Ciência da Computação e Inteligência Synthetic (CSAIL).
Esses algoritmos são frequentemente usados em sistemas de recomendação on-line. Pesquise um produto em um website de comércio eletrônico e provavelmente você verá rapidamente uma lista de itens relacionados que também pode adicionar ao carrinho. Essa lista é gerada com a ajuda de algoritmos gráficos que aproveitam o paralelismo para encontrar rapidamente itens relacionados em uma enorme rede de usuários e produtos disponíveis.
Conexões universitárias
Quando adolescente, a única experiência de Shun com computadores foi uma aula de construção de websites no ensino médio. Mais interessado em matemática e ciências naturais do que em tecnologia, ele pretendia se formar em uma dessas disciplinas quando se matriculou na Universidade da Califórnia, em Berkeley.
Mas durante seu primeiro ano, um amigo recomendou que ele fizesse uma introdução às aulas de ciência da computação. Embora não tivesse certeza do que esperar, ele decidiu se inscrever.
“Eu me apaixonei por programar e projetar algoritmos. Mudei para a ciência da computação e nunca mais olhei para trás”, lembra ele.
Esse curso inicial de ciência da computação foi individualizado, então Shun aprendeu sozinho a maior parte do materials. Ele gostou dos aspectos lógicos do desenvolvimento de algoritmos e do curto ciclo de suggestions dos problemas da ciência da computação. Shun poderia inserir suas soluções no computador e ver imediatamente se estava certo ou errado. E os erros nas soluções erradas o guiariam para a resposta certa.
“Sempre achei divertido construir coisas e, na programação, você constrói soluções que fazem algo útil. Isso me atraiu”, acrescenta.
Após a formatura, Shun passou algum tempo na indústria, mas emblem percebeu que queria seguir carreira acadêmica. Na universidade, ele sabia que teria liberdade para estudar problemas que lhe interessassem.
Entrando em gráficos
Matriculou-se como estudante de pós-graduação na Carnegie Mellon College, onde concentrou sua pesquisa em algoritmos aplicados e computação paralela.
Na graduação, Shun fez aulas teóricas de algoritmos e cursos práticos de programação, mas os dois mundos não se conectavam. Ele queria conduzir pesquisas que combinassem teoria e aplicação. Algoritmos paralelos foram o ajuste perfeito.
“Na computação paralela, é preciso se preocupar com as aplicações práticas. O objetivo da computação paralela é acelerar as coisas na vida actual; portanto, se seus algoritmos não forem rápidos na prática, eles não serão tão úteis”, diz ele.
Na Carnegie Mellon, ele conheceu conjuntos de dados gráficos, onde objetos em uma rede são modelados como vértices conectados por arestas. Ele se sentiu atraído pelas muitas aplicações desses tipos de conjuntos de dados e pelo desafiador problema de desenvolver algoritmos eficientes para lidar com eles.
Depois de concluir uma bolsa de pós-doutorado em Berkeley, Shun procurou um cargo docente e decidiu ingressar no MIT. Ele vinha colaborando com vários membros do corpo docente do MIT em pesquisas sobre computação paralela e estava entusiasmado por ingressar em um instituto com tamanha experiência.
Em um de seus primeiros projetos após ingressar no MIT, Shun uniu forças com o professor do Departamento de Engenharia Elétrica e Ciência da Computação e membro do CSAIL Saman Amarasinghe, especialista em linguagens de programação e compiladores, para desenvolver uma estrutura de programação para processamento de gráficos conhecida como Gráfico. A estrutura fácil de usar, que gera código eficiente a partir de especificações de alto nível, teve um desempenho cerca de cinco vezes mais rápido do que a segunda melhor abordagem.
“Essa foi uma colaboração muito frutífera. Eu não poderia ter criado uma solução tão poderosa se tivesse trabalhado sozinho”, diz ele.
Shun também expandiu seu foco de pesquisa para incluir algoritmos de agrupamento, que buscam agrupar pontos de dados relacionados. Ele e seus alunos criam algoritmos e estruturas paralelas para resolver rapidamente problemas complexos de clustering, que podem ser usados para aplicações como detecção de anomalias e detecção de comunidades.
Problemas dinâmicos
Recentemente, ele e seus colaboradores têm se concentrado em problemas dinâmicos onde os dados em uma rede gráfica mudam ao longo do tempo.
Quando um conjunto de dados tem bilhões ou trilhões de pontos de dados, executar um algoritmo do zero para fazer uma pequena alteração pode ser extremamente caro do ponto de vista computacional. Ele e seus alunos projetam algoritmos paralelos que processam muitas atualizações ao mesmo tempo, melhorando a eficiência e preservando a precisão.
Mas esses problemas dinâmicos também representam um dos maiores desafios que Shun e sua equipe devem trabalhar para superar. Como não existem muitos conjuntos de dados dinâmicos disponíveis para testar algoritmos, a equipe muitas vezes precisa gerar dados sintéticos que podem não ser realistas e podem prejudicar o desempenho de seus algoritmos no mundo actual.
No remaining, seu objetivo é desenvolver algoritmos de grafos dinâmicos que tenham um desempenho eficiente na prática e, ao mesmo tempo, mantenham as garantias teóricas. Isso garante que serão aplicáveis em uma ampla gama de ambientes, diz ele.
Shun espera que algoritmos paralelos dinâmicos tenham um foco de pesquisa ainda maior no futuro. À medida que os conjuntos de dados continuam a tornar-se maiores, mais complexos e a mudar mais rapidamente, os investigadores terão de construir algoritmos mais eficientes para acompanhar.
Ele também espera que novos desafios surjam com os avanços na tecnologia de computação, uma vez que os pesquisadores precisarão projetar novos algoritmos para aproveitar as propriedades do novo {hardware}.
“Essa é a beleza da pesquisa: posso tentar resolver problemas que outras pessoas não resolveram antes e contribuir com algo útil para a sociedade”, diz ele.