Academic writing skills are crucial for students' success but can feel overwhelming without proper guidance and practice, particularly when writing in a second language. Traditionally, students ask instructors or search dictionaries, which are not universally accessible. Early writing assistants emerged as rule-based systems that focused on detecting misspellings, subject-verb disagreements, and basic punctuation errors but are inaccurate and lack contextual understanding. Machine learning-based assistants demonstrate a strong ability for language understanding but are expensive to train. Large language models (LLMs) have shown remarkable capabilities in generating responses in natural languages based on given prompts, but they have a fundamental limitation in education: they generate essays without teaching, which can have detrimental effects on learning when misused. To address this limitation, we develop CoachGPT, which leverages LLMs to assist academic writing for those with limited educational resources and those who prefer self-paced learning. CoachGPT is an AI agent-based web application that (1) takes instructions from experienced educators (2) converts instructions into sub-tasks, and (3) provides real-time feedback and suggestions using large language models. This unique scaffolding structure makes CoachGPT unique among existing writing assistants. Compared with existing writing assistants, CoachGPT provides a more immersed writing experience with personalized messages. Our user studies prove the usefulness of CoachGPT and the potential of large language models for academic writing.

One key technical challenge in the age of autonomous machines is the programming of autonomous machines, which demands the synergy across multiple domains, including fundamental computer science, computer architecture, and robotics, and requires expertise from both academia and industry. This paper discusses the programming theory and practices tied to producing real-life autonomous machines, and covers aspects from high-level concepts down to low-level code generation in the context of specific functional requirements, performance expectation, and implementation constraints of autonomous machines.

The Fast Fourier Transform (FFT) is one of the most widely used computation kernels. Its performance is highly sensitive to the efficiency of its memory operations. In particular, when the FFT is applied on large problem sizes, the overall performance becomes almost totally memory bound. In those cases, the impact of the algorithm’s computational operations is demoted to minimal. This is probably why existing efforts on optimizing large size FFTs have been focused on optimizing the memory operation efficiency. The widely adopted approach in that regard is to adapt parameters external to the FFT algorithm, such as data layout, system software memory management, etc., to the needs of FFT’s memory operation pattern.In this paper, we look into the FFT internals for a way to mitigate FFT’s memory "boundness". The low efficiency of FFT’s memory operation, to a large degree, is incurred by the many strided data shuffles intrinsic to the algorithm, and made worse by the fact that many of those stride sizes are power-of-two. The strided data shuffling is already one of the hard workload patterns for memory system, and the power-of-two stride sizes make such a memory access pattern even more challenging. This power-of-two strided memory access pattern is the key problem that our paper addresses and represents our main contribution. Our key idea is a complete separation of the logic indexes and the physical indexes of the data internally accessed in FFT. By maintaining an efficient mapping between the logic indexes and the physical indexes through all passes, almost any stride sizes can be used and be further tuned. As the result, FFTs can be correctly carried out without the need for most of those worst power-of-two data shuffles. This greatly improves memory performance and in turn raises the overall performance. We compare our Shuffle-Light FFT (SLFFT) library with FFTW, a very widely used FFT library, and achieve the average speedup on 24.7% on problems sizes from 26to 226, and the maximal speedup of 39.4%.

Sorting text is a commonly encountered computing problem in science and consumer applications. In particular, many of those applications, such as social media or data intelligence types, need to sort huge amount of text data. This motivate the development of parallel text sorting algorithms on modern computer platforms such as GPU. Text sorting and the commonly tackled sorting problems are very different, in that text sorting need to deal with variable key length and highly skewed data distribution, both of which introduce significant challenges to the parallelization of text sorting. Furthermore, GPU’s architecture characteristics is not a native good match of text sorting’s computation pattern. Existing text sorting algorithms are mostly comparison-based, which will lead to thread divergence on GPU, a performance. There are a small number of "radix" sorting algorithms for text. However, they all treat text as character based data, and lead to significant waste on memory space.In this paper, we propose a monotonicity preserving text transformation technique that can map text strings into fixed-length keys. The main innovation is that we carefully keep the original order of the strings during the transformation, i.e., monotonicity preserving, so that transformed keys can be safely radix sorted, in lieu of sorting the original much longer text strings. Our technical can efficiently parallelize the transformed sorting on GPU, and deal with the typical skewed text data distribution in real world applications. Compared with Thrust, a widely used library on GPU, our algorithm outperforms Thrust’s string sorting method with substantial margins. We achieve the average speed up of 2.68 and the max speedup 8.5.

The Convolutional Neural Networks (CNNs) architecture is one of the most widely used deep learning tools. The execution time of CNNs is dominated by the time spent on the convolution steps. Most CNNs implementations adopt an approach that lowers the convolution into a matrix-based operation through the im2col (image to column) process. The transformed convolution then can be easily parallelized with highly efficient BLAS libraries. The contribution of this paper is that we observe significant but intricately patterned data redundancy in this matrix representation of convolution. This redundancy has not been exploited before to improve the performance of CNNs. In this paper, we analyze the origin of the redundancy generated by the im2col process, and reveal a new data pattern to more mathematically concisely describe the matrix representation for convolution. Based on this redundancy-minimized matrix representation, we implement a FFT-based convolution with finer FFT granularity. It achieves on average 23% and maximum 50% speedup over the regular FFT convolution, and on average 93% and maximum 286% speedup over the Im2col+GEMM method from NVIDIA's cuDNN library, one of the most widely used CNNs libraries. Moreover, by replacing existing methods with our new convolution method in a popular deep-learning programming framework Caffe, we observe on average 74% speedup for multiple synthetic CNNs in closer-to-real-world application scenarios and 25% speedup for a variant of the VGG network.

Simultaneous multithreading (SMT) is a unique computer architecture feature to increase the pipeline utilization and therefore, increase the instruction throughput. It improves instruction level throughput by simultaneously filling both vertical and horizontal super-scalar pipeline slots that are left unfilled by native threads. So far SMT has been implemented in hardware. However, hardware SMT implementations have its limitations. First, it is complex and expensive to implement—only higher-end processors are equipped with it even though lower-end processors have same pipeline design as the higher-end variants and might also benefit from it. SMT also introduces great power/energy and area overheads. Moreover, being a hardware feature, SMT is limited by the range and depth of instruction analysis that it can afford at execution time, therefore it is unlikely to benefit from high-level software knowledge about instruction mix and might lose many improvement opportunities. In this paper, we address the limitation of the hardware-based SMT and introduce CSSMT: Compiler based Software Simultaneous Multithreading (SMT). The main contribution of CSSMT is that it exploits high- level program profiles to purposefully "re-mix" instructions from multiple programs to better fill vertical and horizontal super- scalar pipeline slots so that the overall throughput is improved. Furthermore, CSSMT is a software-transformation technique that enables SMT at software level during compilation time. Therefore, it can help overcome the limitation of the hardware-based SMT implementation and is more portable. We test CSSMT with programs from SPEC2006 and NAS benchmarks and achieve up to 12% speedup of execution time (30.7% improvement in terms of multi-program throughput).

Threads usually do not use all available resource son a processor at the same time. For example, some program regions are dominated by memory access instructions while leaving computing units idling, or on the contrary are busy calculating but not using memory I/O. This observation points to an optimization opportunity that if the overall system throughput is the goal, one thread can "piggyback" on another thread without significantly hurting the other thread's performance if the first thread only uses CPU resources that are not heavily used by the other. Clearly the "piggybacking" opportunities are an instruction-level mechanism and OS-level resource management cannot efficiently leverage them. In this paper we propose a new compiler transformation that merges two or multiple program sat instruction level to take advantage of the resource piggybacking opportunities. In particular, we propose program profiling techniques to identify good merging candidates and develop transformation to merge the programs while maintain their original semantics. We evaluated our approach on synthesized benchmarks and 3 NPB benchmarks. In one case, we achieve50% speedup over running the pre-merged benchmarks serially, or 30% speedup over running them in parallel and letting OSmanage their execution.

Fast Fourier Transform (FFT) is frequently invoked in stream processing, e.g., calculating the spectral representation of audio/video frames, and in many cases the inputs are sparse, i.e., most of the inputs' Fourier coefficients being zero. Many sparse FFT algorithms have been proposed to improve FFT's efficiency when inputs are known to be sparse. However, like their "dense" counterparts, existing sparse FFT implementations are input oblivious in the sense that how the algorithms work is not affected by the value of input. The sparse FFT computation on one frame is exactly the same as the computation on the next frame. This paper improves upon existing sparse FFT algorithms by simultaneously exploiting the input sparsity and the similarity between adjacent inputs in stream processing. Our algorithm detects and takes advantage of the similarity between input samples to automatically design and customize sparse filters that lead to better parallelism and performance. More specifically, we develop an efficient heuristic to detect the similarity between the current input to its predecessor in stream processing, and when it is found to be similar, we novelly use the spectral representation of the predecessor to accelerate the sparse FFT computation on the current input. Given a sparse signal that has only $k$ non-zero Fourier coefficients, our algorithm utilizes sparse approximation by tuning several adaptive filters to efficiently package the non-zero Fourier coefficients into a small number of bins which can then be estimated accurately. Therefore, our algorithm has runtime sub-linear to the input size and gets rid of recursive coefficient estimation, both of which improve parallelism and performance. Furthermore, the new heuristic can detect the discontinuities inside the streams and resumes the input adaptation very quickly. We evaluate our input-adaptive sparse FFT implementation on Intel i7 CPU and three NVIDIA GPUs, i.e., NVIDIA GeForce GTX480, Tesla C2070 and Tesla C2075. Our algorithm is faster than previous FFT implementations both in theory and implementation. For inputs with size N=2^{24}, our parallel implementation outperforms FFTW for k up to 2^{18}, which is an order of magnitude higher than prior sparse algorithms. Furthermore, our input adaptive sparse FFT on Tesla C2075 GPU achieves up to 77.2x and 29.3x speedups over 1-thread and 4-thread FFTW, 10.7x, 6.4x, 5.2x speedups against sFFT 1.0, sFFT 2.0, CUFFT, and 6.9x speedup over our sequential CPU performance, respectively.

Graphic Processing Units (GPU) has been proved to be a promising platform to accelerate large size Fast Fourier Transform (FFT) computation. However, GPU performance is severely restricted by the limited memory size and the low bandwidth of data transfer through PCI channel. Additionally, current GPU based FFT implementation only uses GPU to compute, but employs CPU as a mere memory-transfer controller. The computing power of CPUs is wasted. This paper proposes a hybrid parallel framework to use both multi-core CPU and GPU in heterogeneous systems to compute large-scale 2D and 3D FFTs that exceed GPU memory. This work introduces a flexible partitioning scheme that enables concurrent execution of CPU and GPU and integrates several FFT decomposition paradigms to tailor computation and communication. Moreover, our library exposes and exploits previously overlooked parallelism in FFT. Optimal load balancing is automatically achieved from effective performance modeling and empirical tuning process. On average, our large FFT library on GeForce GTX480, Tesla C2070, C2075 is 121% and 145% faster than 4-thread SSE-enabled FFTW and Intel MKL, with max speedups 4.61 and 2.81, respectively.

Parallelism helps performance but at the same time stresses computer resources that are shared among threads. In this paper, we propose a low-overhead hardware counter based profiling method to accurately identify time-relevant contention locations in the program, then these contentions are mitigated so that performance of multithreading tasks can be boosted by the reduction of unnecessary contention cycles. In our preliminary experiment using NAS Parallel Benchmark (NPB), the contention searching algorithm is able to find an severe memory contention loop in FT code. After contention mitigation, more than 10% of the total cycles is eliminated, and the execution time of FT is reduced by 3% at the same time.

Program analysis and program optimization seek to improve program performance. There are optimization techniques which are applied to various scopes such as a source file, function or basic block. Inter-procedural program optimization techniques have the scope of source file and analyze the interaction and relationship between different program functions. The techniques analyze the entire translation unit (typically a source file) and optimize the whole translation unit globally instead of just optimizing inside a function. Analyzing and optimizing an entire translation unit increases compilation time drastically because many factors need to be considered during analysis and optimization. The translation unit size can be quite large, containing many functions. Another issue is that functions in different translation units can be more closely related to each other than to the functions within their translation unit. The main goal of this research is grouping or partitioning of closely related program functions into the same translation unit. Our method profiles an application, determines relationship information between program functions and groups closely related functions together. The source code partitioner method improves the processing time of inter-procedural optimization techniques by applying it to a subset of program functions. Partitioning of program functions by analyzing profiling output shows dramatic decrease in compilation time of programs. Our results show we can improve the compiling time in all tested real world benchmarks.

The optimization of Fast Fourier Transfer (FFT) problems that can fit into GPU memory has been studied extensively. Such on-card FFT libraries like CUFFT can generally achieve much better performance than their counterparts on a CPU, as the data transfer between CPU and GPU is usually not counted in their performance. This high performance, however, is limited by the GPU memory size. When the FFT problem size increases, the data transfer between system and GPU memory can comprise a substantial part of the overall execution time. Therefore, optimizations for FFT problems that outgrow the GPU memory can not bypass the tuning of data transfer between CPU and GPU. However, no prior study has attacked this problem. This paper is the first effort of using GPUs to efficiently compute large FFTs in the CPU memory of a single compute node.

In this paper, a Cooley-Tukey algorithm based multidimensional FFT computation framework on GPU is proposed. This framework generalizes the decomposition of multi-dimensional FFT on GPUs using an I/O tensor representation, and therefore provides a systematic description of possible FFT implementations on GPUs. The framework is geared to the efficiency of multi-dimensional FFT on GPU architectures. In particular, no global transposition among dimensions is performed and some previously unnoticed grouping and commutability of multiple dimensions are highlighted in order to reduce the number of computational kernels and minimize the number of global memory accesses. Important architectural factors and constraints of CUDA, such as coalesced access, bank conflicts and register pressure are also considered in this framework. Moreover, we adapt codelets, a straight-line style FFT implementation originally developed in FFTW, into our framework and prove that they are highly efficient on GPUs.

Fast Fourier Transform in the West(FFTW) is one of the most successful adaptive Discrete Fourier Transform(DFT) libraries. The high-performance of FFTW mostly derives from its empirical search engine that includes all major DFT algorithms. We propose an adaptive model-driven FT performance prediction technique to replace the empirical search engine in FFTW. Our model achieves over 94% of the DFT performance and uses less than 5% of the search time compared with FFTW Exhaustive search on four test platforms.

A raytracer consists in an application capable of tracing rays from a point into a scene in order to determine the closest sphere intersection along the ray's direction.

Automatic library generators, such as ATLAS, Spiral and FFTW, are promising technologies to generate efficient code for different computer architectures. The library generators usually tune programs using two layers of optimizations: the search at the algorithm level, and the optimization for micro kernels. The micro optimizations are important for the performance of library, because the optimized micro kernels are the bases of algorithm level search, and have a great impact on the overall performance of the generated libraries. A successfully optimized micro kernel requires thorough understanding of the interaction between architectural features and highly optimized code. However, literature on library generators focus more on the algorithm level optimization, and usually give only simple discussion of how kernel codes are generated and tuned. As a result, the optimization of micro kernels is still an art that depends on individual expertise, and is insufficiently documented. In this paper, we study the problem of how to generate efficient FFT kernels. We apply a series of micro optimizations, for example, memory hierarchy locality enhancements, to several FFT routines, and use hardware counters to observe the interactions between those optimizations with Intel Pentium 4 and the latest Intel core 2 architecture. We achieve good speedups, and more importantly, we present methods that can be used to generate high-performance FFT kernels on different architectures.

Targeted optimization of program segments can provide an additional program speedup over the highest default optimization level, such as -O3 in GCC. The key challenge is how to automatically search for performance sensitive program segments in a given code, to which a customized set of optimization compiler options could be applied. In this paper we propose a method for automatic detection of performance sensitive program segments based on program segment similarity. First we create a proxy segment template database trained over a set of random input programs. The compiler identifies program segments by correlating them to the pre-build proxy segment templates using the syntax structure and architecture-dependent behavior similarity. We argue that the identified program segments can be custom optimized to improve the overall program performance. The method is evaluated on the Intel XScale PXA255 platform using randomly selected benchmarks. The experimental results show that our method can provide additional speedups over the highest optimization level in GCC 3.3 (-O3) for an arbitrary set of applications.