O filósofo alemão Friedrich Nietzsche disse certa vez que “as cordas invisíveis são os laços mais fortes”. Pode-se pensar em uma “cadeia invisível” como a conexão de coisas relacionadas, como casas na rota de um motorista de entrega, ou negócios abstratos, como compras em uma rede financeira ou usuários de um site de rede social.
O cientista da computação Julian Shun estuda esses tipos de conexões multifacetadas, mas muitas vezes abstratas, 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 recém-nomeado 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 casas na rota de um motorista de entrega ou detectar transações fraudulentas feitas por atores mal-intencionados em uma rede financeira.
Mas com o crescente volume de dados, essas redes cresceram e incluem milhares de milhões ou milhares de milhões de objetos e conexões. Para encontrar soluções eficientes, Shun desenvolveu algoritmos altamente eficientes que usam computação paralela para analisar rapidamente até mesmo os maiores gráficos. 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á procurando algo em um mecanismo de busca ou rede social, deseja obter os resultados o mais rápido possível. Ao tentar identificar transações financeiras fraudulentas em um banco, você deseja fazê-lo em tempo real para minimizar os danos. Algoritmos paralelos podem acelerar as coisas usando mais recursos computacionais”, explicou Shun, que também é pesquisador principal do Laboratório de Ciência da Computação e Inteligência Artificial (CSAIL).
Esses algoritmos são frequentemente usados em sistemas de recomendação online. Pesquise um produto em um site de comércio eletrônico e provavelmente verá rapidamente uma lista de itens relacionados para adicionar ao carrinho. Essa lista é gerada com a ajuda de algoritmos gráficos que usam similaridade para encontrar rapidamente itens relacionados em uma grande rede de usuários e produtos disponíveis.
Links do campus
Quando adolescente, o único conhecimento de Shun sobre computadores era uma aula do ensino médio sobre construção de sites. 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 em seu primeiro ano, um amigo recomendou que ele fizesse uma introdução às aulas de ciência da computação. Embora ela não tivesse certeza do que esperar, ela decidiu se inscrever.
“Adorei programar e projetar algoritmos. Mudei para a ciência da computação e nunca mais olhei para trás”, lembra ele.
Aquele primeiro curso de ciência da computação foi individualizado, então Shun aprendeu muito sozinho. Ele gostou dos aspectos lógicos do desenvolvimento de algoritmos e de curtos ciclos de feedback para problemas de ciência da computação. Shun poderia inserir suas soluções no computador e ver rapidamente se estava certo ou errado. E os erros das soluções incorretas o levariam à resposta correta.
“Sempre achei divertido construir coisas, e na programação você constrói soluções que fazem algo útil. Isso me interessou”, acrescenta.
Depois de se formar, Shun passou algum tempo na indústria, mas logo percebeu que queria seguir carreira acadêmica. Na universidade, ele sabia que teria liberdade para estudar os problemas que lhe interessavam.
Fazendo login em gráficos
Matriculou-se como estudante de pós-graduação na Carnegie Mellon University, onde concentrou sua pesquisa em algoritmos e computação paralela.
Na graduação, Shun teve aulas teóricas de algoritmos e cursos práticos de programação, mas os dois mundos nunca se conectaram. Ele queria fazer pesquisas que combinassem teoria e prática. Os algoritmos correspondentes foram adequados.
“Na computação paralela, você precisa se preocupar com a execução de aplicativos. O objetivo da computação paralela é acelerar as coisas na vida real, portanto, se seus algoritmos não forem rápidos na prática, eles não serão muito úteis”, disse 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 pelos muitos usos 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 uma instituição com esse conhecimento.
Em um de seus primeiros projetos após ingressar no MIT, Shun colaborou com Saman Amarasinghe, professor do Departamento de Engenharia Elétrica e Ciência da Computação e membro do CSAIL, especialista em linguagens de programação e compiladores, para criar uma estrutura de programação de processamento de gráficos conhecida como GraphIt. Uma estrutura fácil de usar, que gera código eficiente a partir de uma especificação de alto nível, executada cinco vezes mais rápido do que a próxima melhor abordagem.
“Essa foi uma colaboração muito frutífera. Eu não teria sido capaz de encontrar uma solução forte se estivesse trabalhando sozinho”, disse 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 estão desenvolvendo algoritmos e estruturas paralelas para resolver rapidamente problemas complexos de agrupamento, que podem ser usados para aplicações como detecção difusa e detecção social.
Problemas de energia
Recentemente, ele e seus colaboradores se concentraram em problemas dinâmicos onde os dados em uma rede gráfica mudam ao longo do tempo.
Se um conjunto de dados tiver bilhões ou bilhões de pontos de dados, executar um algoritmo do zero para fazer uma pequena alteração pode ser muito caro do ponto de vista estatístico. Ele e seus alunos desenvolveram algoritmos paralelos que processam múltiplas atualizações simultaneamente, melhorando a eficiência e preservando a precisão.
Mas estas questões dinâmicas também representam um dos maiores desafios que Shun e a sua equipa devem trabalhar para superar. Como não existem muitos conjuntos de dados dinâmicos disponíveis para testar os algoritmos, a equipe muitas vezes precisa gerar dados sintéticos que podem não ser realistas e podem interferir no desempenho de seus algoritmos no mundo real.
Em última análise, seu objetivo é desenvolver algoritmos de gráficos dinâmicos que funcionem bem e ao mesmo tempo respeitem as garantias teóricas. Isso garante que eles funcionarão em uma ampla variedade de ambientes, diz ele.
Shun espera que algoritmos paralelos se tornem um foco de pesquisa ainda maior no futuro. À medida que os conjuntos de dados continuam a ficar maiores, mais complexos e a mudar mais rapidamente, os investigadores terão de desenvolver algoritmos mais eficientes para acompanhar.
Ele também espera que novos desafios surjam com os avanços na tecnologia computacional, já que os pesquisadores precisarão projetar novos algoritmos para usar novas arquiteturas de hardware.
“Essa é a beleza da pesquisa – tento resolver problemas que outras pessoas não resolveram e acrescentar algo útil à sociedade”, diz ele.
