Supporting intra-task parallelism in real-time multiprocessor systems

Os sistemas de tempo real modernos geram, cada vez mais, cargas computacionais pesadas e dinâmicas, começando-se a tornar pouco expectável que sejam implementados em sistemas uniprocessador. Na verdade, a mudança de sistemas com um único processador para sistemas multi- processador pode ser vista, tanto no domínio geral, como no de sistemas embebidos, como uma forma eficiente, em termos energéticos, de melhorar a performance das aplicações. Simultaneamente, a proliferação das plataformas multi-processador transformaram a programação paralela num tópico de elevado interesse, levando o paralelismo dinâmico a ganhar rapidamente popularidade como um modelo de programação. A ideia, por detrás deste modelo, é encorajar os programadores a exporem todas as oportunidades de paralelismo através da simples indicação de potenciais regiões paralelas dentro das aplicações. Todas estas anotações são encaradas pelo sistema unicamente como sugestões, podendo estas serem ignoradas e substituídas, por construtores sequenciais equivalentes, pela própria linguagem. Assim, o modo como a computação é na realidade subdividida, e mapeada nos vários processadores, é da responsabilidade do compilador e do sistema computacional subjacente. Ao retirar este fardo do programador, a complexidade da programação é consideravelmente reduzida, o que normalmente se traduz num aumento de produtividade. Todavia, se o mecanismo de escalonamento subjacente não for simples e rápido, de modo a manter o overhead geral em níveis reduzidos, os benefícios da geração de um paralelismo com uma granularidade tão fina serão meramente hipotéticos. Nesta perspetiva de escalonamento, os algoritmos que empregam uma política de workstealing são cada vez mais populares, com uma eficiência comprovada em termos de tempo, espaço e necessidades de comunicação. Contudo, estes algoritmos não contemplam restrições temporais, nem outra qualquer forma de atribuição de prioridades às tarefas, o que impossibilita que sejam diretamente aplicados a sistemas de tempo real. Além disso, são tradicionalmente implementados no runtime da linguagem, criando assim um sistema de escalonamento com dois níveis, onde a previsibilidade, essencial a um sistema de tempo real, não pode ser assegurada. Nesta tese, é descrita a forma como a abordagem de work-stealing pode ser resenhada para cumprir os requisitos de tempo real, mantendo, ao mesmo tempo, os seus princípios fundamentais que tão bons resultados têm demonstrado. Muito resumidamente, a única fila de gestão de processos convencional (deque) é substituída por uma fila de deques, ordenada de forma crescente por prioridade das tarefas. De seguida, aplicamos por cima o conhecido algoritmo de escalonamento dinâmico G-EDF, misturamos as regras de ambos, e assim nasce a nossa proposta: o algoritmo de escalonamento RTWS. Tirando partido da modularidade oferecida pelo escalonador do Linux, o RTWS é adicionado como uma nova classe de escalonamento, de forma a avaliar na prática se o algoritmo proposto é viável, ou seja, se garante a eficiência e escalonabilidade desejadas. Modificar o núcleo do Linux é uma tarefa complicada, devido à complexidade das suas funções internas e às fortes interdependências entre os vários subsistemas. Não obstante, um dos objetivos desta tese era ter a certeza que o RTWS é mais do que um conceito interessante. Assim, uma parte significativa deste documento é dedicada à discussão sobre a implementação do RTWS e à exposição de situações problemáticas, muitas delas não consideradas em teoria, como é o caso do desfasamento entre vários mecanismo de sincronização. Os resultados experimentais mostram que o RTWS, em comparação com outro trabalho prático de escalonamento dinâmico de tarefas com restrições temporais, reduz significativamente o overhead de escalonamento através de um controlo de migrações, e mudanças de contexto, eficiente e escalável (pelo menos até 8 CPUs), ao mesmo tempo que alcança um bom balanceamento dinâmico da carga do sistema, até mesmo de uma forma não custosa. Contudo, durante a avaliação realizada foi detetada uma falha na implementação do RTWS, pela forma como facilmente desiste de roubar trabalho, o que origina períodos de inatividade, no CPU em questão, quando a utilização geral do sistema é baixa. Embora o trabalho realizado se tenha focado em manter o custo de escalonamento baixo e em alcançar boa localidade dos dados, a escalonabilidade do sistema nunca foi negligenciada. Na verdade, o algoritmo de escalonamento proposto provou ser bastante robusto, não falhando qualquer meta temporal nas experiências realizadas. Portanto, podemos afirmar que alguma inversão de prioridades, causada pela sub-política de roubo BAS, não compromete os objetivos de escalonabilidade, e até ajuda a reduzir a contenção nas estruturas de dados. Mesmo assim, o RTWS também suporta uma sub-política de roubo determinística: PAS. A avaliação experimental, porém, não ajudou a ter uma noção clara do impacto de uma e de outra. No entanto, de uma maneira geral, podemos concluir que o RTWS é uma solução promissora para um escalonamento eficiente de tarefas paralelas com restrições temporais.

Anotação colaborativa de conteúdos utilizando jogos com propósito

Com o crescimento da informação disponível na Web, arquivos pessoais e profissionais, protagonizado tanto pelo aumento da capacidade de armazenamento de dados, como pelo aumento exponencial da capacidade de processamento dos computadores, e do fácil acesso a essa mesma informação, um enorme fluxo de produção e distribuição de conteúdos audiovisuais foi gerado. No entanto, e apesar de existirem mecanismos para a indexação desses conteúdos com o objectivo de permitir a pesquisa e acesso aos mesmos, estes apresentam normalmente uma grande complexidade algorítmica ou exigem a contratação de pessoal altamente qualificado, para a verificação e categorização dos conteúdos. Nesta dissertação pretende-se estudar soluções de anotação colaborativa de conteúdos e desenvolver uma ferramenta que facilite a anotação de um arquivo de conteúdos audiovisuais. A abordagem implementada é baseada no conceito dos “Jogos com Propósito” (GWAP – Game With a Purpose) e permite que os utilizadores criem tags (metadatos na forma de palavras-chave) de forma a atribuir um significado a um objecto a ser categorizado. Assim, e como primeiro objectivo, foi desenvolvido um jogo com o propósito não só de entretenimento, mas também que permita a criação de anotações audiovisuais perante os vídeos que são apresentados ao jogador e, que desta forma, se melhore a indexação e categorização dos mesmos. A aplicação desenvolvida permite ainda a visualização dos conteúdos e metadatos categorizados, e com o objectivo de criação de mais um elemento informativo, permite a inserção de um like num determinado instante de tempo do vídeo. A grande vantagem da aplicação desenvolvida reside no facto de adicionar anotações a pontos específicos do vídeo, mais concretamente aos seus instantes de tempo. Trata-se de uma funcionalidade nova, não disponível em outras aplicações de anotação colaborativa de conteúdos audiovisuais. Com isto, o acesso aos conteúdos será bastante mais eficaz pois será possível aceder, por pesquisa, a pontos específicos no interior de um vídeo.

Pré-processamento e Tag automático de imagens em ambiente móvel e web, aplicado a um sistema de informação geográfica

No panorama socioeconómico atual, a contenção de despesas e o corte no financiamento de serviços secundários consumidores de recursos conduzem à reformulação de processos e métodos das instituições públicas, que procuram manter a qualidade de vida dos seus cidadãos através de programas que se mostrem mais eficientes e económicos. O crescimento sustentado das tecnologias móveis, em conjunção com o aparecimento de novos paradigmas de interação pessoa-máquina com recurso a sensores e sistemas conscientes do contexto, criaram oportunidades de negócio na área do desenvolvimento de aplicações com vertente cívica para indivíduos e empresas, sensibilizando-os para a disponibilização de serviços orientados ao cidadão. Estas oportunidades de negócio incitaram a equipa do projeto a desenvolver uma plataforma de notificação de problemas urbanos baseada no seu sistema de informação geográfico para entidades municipais. O objetivo principal desta investigação foca a idealização, conceção e implementação de uma solução completa de notificação de problemas urbanos de caráter não urgente, distinta da concorrência pela facilidade com que os cidadãos são capazes de reportar situações que condicionam o seu dia-a-dia. Para alcançar esta distinção da restante oferta, foram realizados diversos estudos para determinar características inovadoras a implementar, assim como todas as funcionalidades base expectáveis neste tipo de sistemas. Esses estudos determinaram a implementação de técnicas de demarcação manual das zonas problemáticas e reconhecimento automático do tipo de problema reportado nas imagens, ambas desenvolvidas no âmbito deste projeto. Para a correta implementação dos módulos de demarcação e reconhecimento de imagem, foram feitos levantamentos do estado da arte destas áreas, fundamentando a escolha de métodos e tecnologias a integrar no projeto. Neste contexto, serão apresentadas em detalhe as várias fases que constituíram o processo de desenvolvimento da plataforma, desde a fase de estudo e comparação de ferramentas, metodologias, e técnicas para cada um dos conceitos abordados, passando pela proposta de um modelo de resolução, até à descrição pormenorizada dos algoritmos implementados. Por último, é realizada uma avaliação de desempenho ao par algoritmo/classificador desenvolvido, através da definição de métricas que estimam o sucesso ou insucesso do classificador de objetos. A avaliação é feita com base num conjunto de imagens de teste, recolhidas manualmente em plataformas públicas de notificação de problemas, confrontando os resultados obtidos pelo algoritmo com os resultados esperados.

Providing Adaptation for an Adaptive Hypermedia System

O ensino à distância cresceu consideravelmente nos últimos anos e a tendência é para que continue a crescer em anos vindouros. No entanto, enquanto que a maioria das plataformas de ensino à distância utilizam a mesma abordagem de ensino para todos os utilizadores, os estudantes que as usam são na realidade pessoas de diferentes culturas, locais, idades e géneros, e que possuem diferentes níveis de educação. Ao contrário do ensino à distância tradicional, os sistemas de hipermédia adaptativa educacional adaptam interface, apresentação de conteúdos e navegação, entre outros, às características, necessidades e interesses específicos de diferentes utilizadores. Apesar da investigação na área de sistemas de hipermédia adaptativa já estar bastante desenvolvida, é necessário efetuar mais desenvolvimento e experimentação de modo a determinar quais são os aspetos mais eficazes destes sistemas e avaliar o seu sucesso. A Plataforma de Aprendizagem Colaborativa da Matemática (PCMAT) é um sistema de hipermédia adaptativa educacional com uma abordagem construtivista, que foi desenvolvido com o objetivo de contribuir para a investigação na área de sistemas de hipermédia adaptativa. A plataforma avalia o conhecimento do utilizador e apresenta conteúdos e atividades adaptadas às características e estilo de aprendizagem dominante de estudantes de matemática do segundo ciclo. O desenvolvimento do PCMAT tem também o propósito de auxiliar os alunos Portugueses com a aprendizagem da matemática. De acordo com o estudo PISA 2012 da OCDE [OECD, 2014], o desempenho dos alunos Portugueses na área da matemática melhorou em relação à edição anterior do estudo, mas os resultados obtidos permanecem abaixo da média da OCDE. Por este motivo, uma das finalidades deste projeto é desenvolver um sistema de hipermédia adaptativa que, ao adequar o ensino da matemática às necessidades específicas de cada aluno, os assista com a aquisição de conhecimento. A adaptação é efetuada pelo sistema usando a informação constante no modelo do utilizador para definir um grafo de conceitos do domínio específico. Este grafo é adaptado do modelo do domínio e utilizado para dar resposta às necessidades particulares de cada aluno. Embora a trajetória inicial seja definida pelo professor, o percurso percorrido no grafo por cada aluno é determinado pela sua interação com o sistema, usando para o efeito a representação do conhecimento do aluno e outras características disponíveis no modelo do utilizador, assim como avaliação progressiva. A adaptação é conseguida através de alterações na apresentação de conteúdos e na estrutura e anotações das hiperligações. A apresentação de conteúdos é alterada mostrando ou ocultando cada um dos vários fragmentos que compõe as páginas dum curso. Estes fragmentos são compostos por diferentes objetos de aprendizagem, tais como exercícios, figuras, diagramas, etc. As mudanças efetuadas na estrutura e anotações das hiperligações têm o objetivo de guiar o estudante, apontando-o na direção do conhecimento mais relevante e mantendo-o afastado de informação inadequada. A escolha de objectos de aprendizagem adequados às características particulares de cada aluno é um aspecto essencial do modelo de adaptação do PCMAT. A plataforma inclui para esse propósito um módulo responsável pela recomendação de objectos de aprendizagem, e um módulo para a pesquisa e recuperação dos mesmos. O módulo de recomendação utiliza lógica Fuzzy para converter determinados atributos do aluno num conjunto de parâmetros que caracterizam o objecto de aprendizagem que idealmente deveria ser apresentado ao aluno. Uma vez que o objecto “ideal” poderá não existir no repositório de objectos de aprendizagem do sistema, esses parâmetros são utilizados pelo módulo de pesquisa e recuperação para procurar e devolver ao módulo de recomendação uma lista com os objectos que mais se assemelham ao objecto “ideal”. A pesquisa é feita numa árvore k-d usando o algoritmo k-vizinhos mais próximos. O modelo de recomendação utiliza a lista devolvida pelo módulo de pesquisa e recuperação para seleccionar o objecto de aprendizagem mais apropriado para o aluno e processa-o para inclusão numa das páginas Web do curso. O presente documento descreve o trabalho desenvolvido no âmbito do projeto PCMAT (PTDS/CED/108339/2008), dando relevância à adaptação de conteúdos.