We propose two efficient automatic differentiation (AD) schemes to compute incrementally Taylor series and System Jacobian for solving differential-algebraic equations (DAEs) by Taylor series. Our schemes are based on topological ordering of a DAE's computational graph and then partitioning the topologically sorted nodes using structural information obtained from the DAE. Solving a DAE by Taylor series is carried out in stages. From one stage to another, partitions of the computational graph are incrementally activated so that we can reuse Taylor coefficients and gradients computed in previous stages. As a result, the computational complexity of evaluating a System Jacobian is independent of the number of stages. We also develop a common subexpression elimination (CSE) method to build a compact computational graph through operator overloading. The CSE method is of linear time complexity, which makes it suitable as a preprocessing step for general operator overloaded computing. By applying CSE, all successive overloaded computation can save time and memory. Furthermore, the computational graph of a DAE reveals its internal sparsity structure. Based on it, we devise an algorithm to propagate gradients in the forward mode of AD using compressed vectors. This algorithm can save both time and memory when computing the System Jacobian for sparse DAEs. We have integrated our approaches into the \daets solver. Computational results show multiple-fold speedups against two popular AD tools, \FAD~and ADOL-C, when solving various sparse and dense DAEs. / Thesis / Master of Science (MSc)

<p>IDCT (Inverse Discrete Cosine Transform) is a common algorithm being used with image and sound decompression. The algorithm is a Fourier related transform which can occur in many different types like, one-dimensional, two-dimensional, three-dimensional and many more.</p><p>The goal with this thesis is to create a fast and low effect version of two-dimensional IDCT algorithm, where techniques as multiple-constant multiplication and subexpression sharing plus bit-serial and bit-parallel arithmetic are used.</p><p>The result is a hardware implementation with power consumption at 19,56 mW.</p>

IDCT (Inverse Discrete Cosine Transform) is a common algorithm being used with image and sound decompression. The algorithm is a Fourier related transform which can occur in many different types like, one-dimensional, two-dimensional, three-dimensional and many more. The goal with this thesis is to create a fast and low effect version of two-dimensional IDCT algorithm, where techniques as multiple-constant multiplication and subexpression sharing plus bit-serial and bit-parallel arithmetic are used. The result is a hardware implementation with power consumption at 19,56 mW.

O carcinoma epidermóide de pênis (CEP) representa 95% das neoplasias penianas e afeta quase sempre pacientes não circuncidados estando muitas vezes associado à falta de higiene local adequada e à fimose. No Brasil a sua incidência é de 2,7 % porém em algumas áreas do país pode chegar a 17% dos casos diagnosticados por ano. O tumor pode ocorrer em qualquer parte do órgão sexual masculino e o tipo de estadiamento empregado é controverso. A classificação de Broders é a mais utilizada. Estudos sugerem a relação entre o desenvolvimento do carcinoma de pênis com a infecção por HPV (Papiloma Vírus Humano). O método de avaliação dos linfonodos inguinais permanece controverso sendo difícil a diferenciação entre linfadenomegalia inflamatória reacional e metastática. O exame físico não é um preditor confiável do comprometimento linfonodal pois pacientes com linfonodos palpáveis podem não apresentar metástases. Há poucas publicações sobre os mecanismos moleculares envolvidos na gênese e progressão do CEP. Apesar de vários marcadores terem sido avaliados, atualmente a aplicação clínica destes é limitada. A maior parte dos marcadores estudados requer procedimentos invasivos para obtenção do tecido tumoral. Existe a necessidade de encontrar através de uma técnica pouco invasiva marcadores tumorais circulantes capazes de diferenciar portadores de CEP com e sem envolvimento metastático. Neste tipo de neoplasia, a descoberta de biomarcadores que avaliem o prognóstico é relevante, pois o exame físico não é um indicador confiável do comprometimento linfonodal e da sobrevida.Os objetivos foram 1) revisar e discutir a epidemiologia, a etiologia, os diversos tipos de abordagem cirúrgica e as controvérsias no tratamento cirúrgico do câncer de pênis 2) investigar através da plataforma ClinProt/ MALDI / TOF a presença de marcadores plasmáticos capazes de discriminar indivíduos saudáveis de pacientes afetados por carcinoma epidermóide de pênis (CEP) 3) avaliar a importância destes marcadores na evolução da doença. Foram coletados e analisados pela plataforma ClinProt / MALDI / TOF o plasma de 36 indivíduos saudáveis e 25 pacientes com CEP invasivo, submetidos a tratamento cirúrgico entre junho de 2010 e junho de 2011, nos serviços de urologia do Instituto Nacional de Câncer e do Hospital Mário Kröeff (Rio de Janeiro). Nossos resultados apontaram para um conjunto de dois peptídeos (A = m / z 1897,22 + -9 Da e B = m / z 2021,99 + -9 Da) que foram capazes de diferenciar pacientes com CEP de indivíduos controles. Esses peptídeos foram posteriormente identificados como fragmentos C3 e C4 A/B do sistema complemento. A validação cruzada, utilizando toda casuística apresentou 62,5% e 86,76% de sensibilidade e de especificidade, respectivamente, com uma alta sensibilidade (100%) e especificidade (97%) nos pacientes que morreram pela doença. Além disso, os pacientes com envolvimento ganglionar obtiveram uma sensibilidade e uma especificidade de 80 % e 97%, respectivamente. Ficou demonstrado que à medida que a doença progride mais subexpressos está o conjunto de peptídeos quando comparados com indivíduos saudáveis. Estes resultados podem ser úteis como ferramentas para a avaliação do prognóstico destes pacientes. / Squamous cell carcinoma of the penis (SSCP) represents 95% of penile cancers. It affects mostly uncircumcised patients and is often associated with lack of adequate local hygiene and phimosis. In Brazil, the incidence is 2.7% but in some areas of the country can reach 17% of diagnosed cases of cancer per year. The tumor can occur in any part of the sexual organ and the type of staging to be used is controversial. The Broders classification is more often used to classify tumors. Studies suggest the relationship between the development of penile carcinoma and HPV infection (Human Papilloma Virus). The evaluation method of inguinal lymph nodes remains controversial and it is difficult to differentiate inflammatory reaction from metastatic lymphadenopathy. Physical examination is not a reliable predictor of lymph node involvement since patients with palpable lymph nodes can not present metastases. There are few publications about the molecular mechanisms involved in the genesis and progression of the SSCP. Although several markers have been evaluated, currently the clinical application of these is limited. Most of the markers studied require invasive procedures for obtaining tumor tissue. There is a need to find through a minimally invasive technique circulating tumor markers able to differentiate SSCP patients with and without metastatic involvement. In this type ofmalignancythediscovery of biomarkers that assessthe prognosisis relevant since physical examination is not a reliable predictor oflymph node involvementand survival. The objectives of this study were: 1) to review and discuss the epidemiology, etiology, different types of surgical approach and controversies in the surgical treatment of penile cancer 2)to investigate via the platform ClinProt / MALDI / TOF presence of plasma markers able to discriminate healthy subjects from patients affected by squamous cell carcinoma of the penis (SCCP) 3) to evaluate the importance of these markers in disease progression. Between June 2010 and June 2011, plasma samples from 36 healthy subjects and 25 patients with penile carcinoma who underwent surgical treatment in the UrologyServicesofNational Cancer InstituteandMarioKröeffHospital were collected and analyzed by the ClinProt/MALDI/TOF platform. Our results found a cluster of 2 peptides (A=m/z 1897.22 +-9 Da and B=m/z 2021.99 +-9 Da that was able to discriminate patients from controls subjects. These peptides were further identified as C3 and C4 A/B fragments from complement system. Cross validation analysis using the whole casuistic showed 62.5% and 86.76% of sensitivity and specificity, respectively with a very high sensitivity (100%) and specificity (97%) for SCCP patients that have died by disease. Moreover, patients with lymph node involvement present a sensitivity and specificity of 80% and 97%, respectively. The results showed that as the disease progresses more under express are the cluster comparing with healthy subjects. These results may be useful as prognostic toll.

O carcinoma epidermóide de pênis (CEP) representa 95% das neoplasias penianas e afeta quase sempre pacientes não circuncidados estando muitas vezes associado à falta de higiene local adequada e à fimose. No Brasil a sua incidência é de 2,7 % porém em algumas áreas do país pode chegar a 17% dos casos diagnosticados por ano. O tumor pode ocorrer em qualquer parte do órgão sexual masculino e o tipo de estadiamento empregado é controverso. A classificação de Broders é a mais utilizada. Estudos sugerem a relação entre o desenvolvimento do carcinoma de pênis com a infecção por HPV (Papiloma Vírus Humano). O método de avaliação dos linfonodos inguinais permanece controverso sendo difícil a diferenciação entre linfadenomegalia inflamatória reacional e metastática. O exame físico não é um preditor confiável do comprometimento linfonodal pois pacientes com linfonodos palpáveis podem não apresentar metástases. Há poucas publicações sobre os mecanismos moleculares envolvidos na gênese e progressão do CEP. Apesar de vários marcadores terem sido avaliados, atualmente a aplicação clínica destes é limitada. A maior parte dos marcadores estudados requer procedimentos invasivos para obtenção do tecido tumoral. Existe a necessidade de encontrar através de uma técnica pouco invasiva marcadores tumorais circulantes capazes de diferenciar portadores de CEP com e sem envolvimento metastático. Neste tipo de neoplasia, a descoberta de biomarcadores que avaliem o prognóstico é relevante, pois o exame físico não é um indicador confiável do comprometimento linfonodal e da sobrevida.Os objetivos foram 1) revisar e discutir a epidemiologia, a etiologia, os diversos tipos de abordagem cirúrgica e as controvérsias no tratamento cirúrgico do câncer de pênis 2) investigar através da plataforma ClinProt/ MALDI / TOF a presença de marcadores plasmáticos capazes de discriminar indivíduos saudáveis de pacientes afetados por carcinoma epidermóide de pênis (CEP) 3) avaliar a importância destes marcadores na evolução da doença. Foram coletados e analisados pela plataforma ClinProt / MALDI / TOF o plasma de 36 indivíduos saudáveis e 25 pacientes com CEP invasivo, submetidos a tratamento cirúrgico entre junho de 2010 e junho de 2011, nos serviços de urologia do Instituto Nacional de Câncer e do Hospital Mário Kröeff (Rio de Janeiro). Nossos resultados apontaram para um conjunto de dois peptídeos (A = m / z 1897,22 + -9 Da e B = m / z 2021,99 + -9 Da) que foram capazes de diferenciar pacientes com CEP de indivíduos controles. Esses peptídeos foram posteriormente identificados como fragmentos C3 e C4 A/B do sistema complemento. A validação cruzada, utilizando toda casuística apresentou 62,5% e 86,76% de sensibilidade e de especificidade, respectivamente, com uma alta sensibilidade (100%) e especificidade (97%) nos pacientes que morreram pela doença. Além disso, os pacientes com envolvimento ganglionar obtiveram uma sensibilidade e uma especificidade de 80 % e 97%, respectivamente. Ficou demonstrado que à medida que a doença progride mais subexpressos está o conjunto de peptídeos quando comparados com indivíduos saudáveis. Estes resultados podem ser úteis como ferramentas para a avaliação do prognóstico destes pacientes. / Squamous cell carcinoma of the penis (SSCP) represents 95% of penile cancers. It affects mostly uncircumcised patients and is often associated with lack of adequate local hygiene and phimosis. In Brazil, the incidence is 2.7% but in some areas of the country can reach 17% of diagnosed cases of cancer per year. The tumor can occur in any part of the sexual organ and the type of staging to be used is controversial. The Broders classification is more often used to classify tumors. Studies suggest the relationship between the development of penile carcinoma and HPV infection (Human Papilloma Virus). The evaluation method of inguinal lymph nodes remains controversial and it is difficult to differentiate inflammatory reaction from metastatic lymphadenopathy. Physical examination is not a reliable predictor of lymph node involvement since patients with palpable lymph nodes can not present metastases. There are few publications about the molecular mechanisms involved in the genesis and progression of the SSCP. Although several markers have been evaluated, currently the clinical application of these is limited. Most of the markers studied require invasive procedures for obtaining tumor tissue. There is a need to find through a minimally invasive technique circulating tumor markers able to differentiate SSCP patients with and without metastatic involvement. In this type ofmalignancythediscovery of biomarkers that assessthe prognosisis relevant since physical examination is not a reliable predictor oflymph node involvementand survival. The objectives of this study were: 1) to review and discuss the epidemiology, etiology, different types of surgical approach and controversies in the surgical treatment of penile cancer 2)to investigate via the platform ClinProt / MALDI / TOF presence of plasma markers able to discriminate healthy subjects from patients affected by squamous cell carcinoma of the penis (SCCP) 3) to evaluate the importance of these markers in disease progression. Between June 2010 and June 2011, plasma samples from 36 healthy subjects and 25 patients with penile carcinoma who underwent surgical treatment in the UrologyServicesofNational Cancer InstituteandMarioKröeffHospital were collected and analyzed by the ClinProt/MALDI/TOF platform. Our results found a cluster of 2 peptides (A=m/z 1897.22 +-9 Da and B=m/z 2021.99 +-9 Da that was able to discriminate patients from controls subjects. These peptides were further identified as C3 and C4 A/B fragments from complement system. Cross validation analysis using the whole casuistic showed 62.5% and 86.76% of sensitivity and specificity, respectively with a very high sensitivity (100%) and specificity (97%) for SCCP patients that have died by disease. Moreover, patients with lymph node involvement present a sensitivity and specificity of 80% and 97%, respectively. The results showed that as the disease progresses more under express are the cluster comparing with healthy subjects. These results may be useful as prognostic toll.

The multiple constant multiplication (MCM) operation is a fundamental operation in digital signal processing (DSP) and digital image processing (DIP). Examples of the MCM are in finite impulse response (FIR) and infinite impulse response (IIR) filters, matrix multiplication, and transforms. The aim of this work is minimizing the complexity of the MCM operation using common subexpression elimination (CSE) technique and redundant number representations. The CSE technique searches and eliminates common digit patterns (subexpressions) among MCM coefficients. More common subexpressions can be found by representing the MCM coefficients using redundant number representations. A CSE algorithm is proposed that works on a type of redundant numbers called the zero-dominant set (ZDS). The ZDS is an extension over the representations of minimum number of non-zero digits called minimum Hamming weight (MHW). Using the ZDS improves CSE algorithms' performance as compared with using the MHW representations. The disadvantage of using the ZDS is it increases the possibility of overlapping patterns (digit collisions). In this case, one or more digits are shared between a number of patterns. Eliminating a pattern results in losing other patterns because of eliminating the common digits. A pattern preservation algorithm (PPA) is developed to resolve the overlapping patterns in the representations. A tree and graph encoders are proposed to generate a larger space of number representations. The algorithms generate redundant representations of a value for a given digit set, radix, and wordlength. The tree encoder is modified to search for common subexpressions simultaneously with generating of the representation tree. A complexity measure is proposed to compare between the subexpressions at each node. The algorithm terminates generating the rest of the representation tree when it finds subexpressions with maximum sharing. This reduces the search space while minimizes the hardware complexity. A combinatoric model of the MCM problem is proposed in this work. The model is obtained by enumerating all the possible solutions of the MCM that resemble a graph called the demand graph. Arc routing on this graph gives the solutions of the MCM problem. A similar arc routing is found in the capacitated arc routing such as the winter salting problem. Ant colony optimization (ACO) meta-heuristics is proposed to traverse the demand graph. The ACO is simulated on a PC using Python programming language. This is to verify the model correctness and the work of the ACO. A parallel simulation of the ACO is carried out on a multi-core super computer using C++ boost graph library.